Теория графов - сопоставления

Граф соответствия - это подграф графа, в котором нет смежных друг с другом ребер. Просто между любыми двумя ребрами не должно быть общей вершины.

Соответствие

Пусть 'G' = (V, E) - граф. Подграф называется паросочетанием M (G),if each vertex of G is incident with at most one edge in M, т.е.

deg (V) ≤ 1 ∀ V ∈ G

это означает, что в графе паросочетания M (G) вершины должны иметь степень 1 или 0, причем ребра должны быть инцидентны графу G.

Notation - М (G)

Example

В сопоставлении

если deg (V) = 1, то (V) называется согласованным

если deg (V) = 0, то (V) не совпадает.

В сопоставлении нет двух смежных ребер. Это потому, что если любые два ребра смежны, то степень вершины, которая соединяет эти два ребра, будет иметь степень 2, что нарушает правило сопоставления.

Максимальное соответствие

Паросочетание M графа G называется максимальным if no other edges of ‘G’ can be added to M.

Example

M1, M2, M3 из вышеприведенного графика являются максимальным паросочетанием G.

Максимальное соответствие

Он также известен как наибольшее максимальное соответствие. Максимальное соответствие определяется как максимальное соответствие с максимальным количеством ребер.

Количество ребер в максимальном совпадении G называется его matching number.

Example

Для графа, приведенного в приведенном выше примере, M1 и M2 являются максимальным соответствием 'G', и его номер совпадения равен 2. Следовательно, используя граф G, мы можем сформировать только подграфы с максимум двумя ребрами. Следовательно, у нас есть совпадающее число как два.

Идеальное соответствие

Совпадение (M) графа (G) называется полным совпадением, если каждая вершина графа g (G) инцидентна ровно одному ребру сопоставления (M), т. Е.

град (V) = 1 ∀ V

Степень каждой вершины в подграфе должна иметь степень 1.

Example

На следующих графиках M1 и M2 являются примерами идеального согласования G.

Note - Каждое идеальное совпадение графа также является максимальным совпадением графа, потому что нет возможности добавить еще одно ребро в идеальный совпадающий граф.

Максимальное соответствие графика не обязательно должно быть идеальным. Если граф «G» имеет полное совпадение, то количество вершин | V (G) | даже. Если он нечетный, то последняя вершина соединяется с другой вершиной, и, наконец, остается одна вершина, которая не может быть соединена ни с какой другой вершиной, для которой степень равна нулю. Это явно нарушает принцип идеального соответствия.

Example