В чем разница между изоморфизмом подграфа и мономорфизмом подграфа?
В одном из проектов, над которым я работал, возник вопрос об изоморфизме и мономорфизме.
Немного предыстории: я не специалист по теории графов, и у меня нет формального обучения этому. Но эта тема очень важна в химии, где химики ожидают, что в системах поиска по структуре, которые они используют, будет происходить конкретный тип подграфа.
Если целевой граф A имеет n узлов и m ребер, то химик будет принимать совпадения подграфа, в которых граф B запроса имеет n узлов и m-1 ребер. Единственным требованием будет то, что каждое ребро в B должно присутствовать в A. Например, линейная цепочка из 6 узлов должна соответствовать циклу из 6 узлов.
Является ли этот вид совпадающего изоморфизма или мономорфизма? Может быть, что-то еще вообще?
4 ответа
Пусть G1, G2 - графы, составленные из множеств вершин и ребер V1, V2 и E1, E2 соответственно.
G2 изоморфна подграфу G1, если существует однозначное отображение между каждой вершиной V2 и вершиной в V1 и между каждым ребром в E2 и некоторым ребром в E1. Таким образом, чтобы быть изоморфным, вам нужно иметь точное соответствие, в том числе, если граф включает более одного ребра между узлами.
G2 мономорфна, если существует такое отображение между вершинами, и существует ребро между всеми вершинами в V2, для которого есть соответствующее ребро в V1. Но пока существует хотя бы одно преимущество, этого достаточно.
Вот хорошее описание пакета из comp.lang.python.
Здесь есть несоответствие между терминами Math и CS. Из математики вы получаете два термина:
Изоморфизм подграфа. Пусть H = (VH, EH) и G = (V, E) графы. f: VH → V является изоморфизмом подграфа, если (u, v) ∈ EH, то (f(u), f(v)) ∈ E. H изоморфен подграфу G
индуцированный изоморфизм подграфа: пусть H = (VH, EH) и G = (V, E) графы. f: VH → V является изоморфизмом индуцированного подграфа, если (u, v) ∈ EH, то (f (u), f (v)) ∈ E. А если (u, v) нет и элемент EH, то (f (u), f (v)) не является элементом в E. H изоморфен индуцированному подграфу в G
Определения из http://theory.stanford.edu/~virgi/cs267/lecture1.pdf. Они эквивалентны тому, что я нашел в "Первом курсе теории графов".
Заметим, что оба они являются инъективными гомоморфизмами между графами или графовым мономорфизмом.
Переход к CS и, в частности, проблема изоморфизма подграфа. Насколько я понимаю, алгоритм изоморфизма подграфа определяет, существует ли функция, удовлетворяющая (2) сверху.
Граф мономорфизма соответствует (1).
Определения CS взяты из алгоритма VF2, я не знаю, насколько широко это использование. При поиске правильного алгоритма для проекта кажется, что все еще есть некоторая неопределенность, и не все проекты используют одинаковые определения.
Возьмите этот ответ с небольшой долей соли. раздел 2 определяет изоморфизм графа-подграфа как концептуально идентичный (1), который указывает, что я что-то упустил.
Мономорфизм.
Мономорфизм из одного графа ("B") в другой граф ("A") эквивалентен изоморфизму из B в подграф A.
В примере говорится, что любой путь n вершин ("цепочка") мономорфен циклу n вершин. Это также будет мономорфно n+1 циклу вершин или n+k для любого k.
Гомоморфизм неориентированных графов h: H -> G называется мономорфизмом, когда h на вершинах является инъективной функцией. Как гомоморфизм графа h, конечно, отображает ребра в ребра, но не требуется, чтобы ребро h(v0)-h(v1) отражалось в H.
Случай ориентированных графов аналогичен.