В чем разница между подграфом изоморфизм и подграф мономорфизм?

Question

В одном из проектов, над которым я работал, возникла тема изоморфизм против мономорфизма .

Немного предыстории: я не специалист по теории графов, и у меня нет формального обучения этому. Но эта тема очень важна в химии, где химики ожидают, что в используемых ими поисковых системах структур будет осуществляться поиск соответствия подграфа определенного типа.

Если целевой граф A имеет n узлов и m ребер, то химик будет принимать совпадения подграфа, в которых граф B запроса имеет n узлов и m-1 ребер. Единственное требование состоит в том, чтобы каждое ребро в B присутствовало в A. Например, линейная цепочка из 6 узлов должна соответствовать циклу из 6 узлов.

Является ли этот вид совпадающего изоморфизма или мономорфизма? Может быть, что-то еще вообще?

Answer 1

Пусть G1, G2 - графы, составленные из наборов вершин и ребер V1, V2 и E1, E2 соответственно.

G2 изоморфна подграфу G1, если существует однозначное отображение между каждой вершиной V2 и вершиной в V1 и между каждым ребром в E2 и некоторым ребром в E1. Таким образом, чтобы быть изоморфным, вам нужно иметь точное соответствие, в том числе, если граф содержит более одного ребра между узлами.

G2 является мономорфным , если существует такое отображение между вершинами, и существует ребро между всеми вершинами в V2, для которого есть соответствующее ребро в V1. Но пока существует хотя бы одно ребро, этого достаточно.

Вот хорошее описание пакета от comp.lang.python .

Answer 2

Мономорфизм.

Мономорфизм из одного графа ("B") в другой граф ("A") эквивалентен изоморфизму из B в подграф A.

В примере говорится, что любой путь n вершин («цепочка») является мономорфным циклу n вершин. Это также будет мономорфно n + 1 циклу вершин или n + k для любого k.

Answer 3

Гомоморфизм неориентированных графов h: H -> G называется мономорфизмом, когда h на вершинах является инъективной функцией. Поскольку гомоморфизм графа h, конечно, отображает ребра в ребра, но не требуется, чтобы ребро h (v0) -h (v1) отражалось в H.

Случай ориентированных графов аналогичен.

Answer 4

Здесь есть несоответствие между терминами Math и CS. Из математики вы получаете два термина:

1. изоморфизм подграфа: Пусть H = (VH, EH) и G = (V, E) графы. f: VH → V является изоморфизмом подграфа, если (u, v) ∈ EH, то (f (u), f (v)) ∈ E. H изоморфен подграфу G

2. индуцированный изоморфизм подграфа: Пусть 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, я не знаю, насколько широко это использование. При поиске правильного алгоритма для проекта кажется, что все еще есть некоторая неопределенность, и не все проекты используют одинаковые определения.

Примите этот ответ с крошкой соли http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5342&rep=rep1&type=pdf перечисляет мономорфизм как отдельный от изоморфизма графа-подграфа во введении, но в разделе 2 определяет изоморфизм графа-подграфа как концептуально идентичный (1), который указывает, что я что-то упустил.