Теория графов - изоморфизм

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

Изоморфные графы

Два графа G 1 и G 2 называются изоморфными, если -

  • Количество компонентов (вершин и ребер) у них одинаковое.

  • Их краевое соединение сохраняется.

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

There exists a function ‘f’ from vertices of G1 to vertices of G2
   [f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.

Note

Если G 1 ≡ G 2, то -

| V (G 1 ) | = | V (G 2 ) |

| E (G 1 ) | = | E (G 2 ) |

Последовательности степеней G 1 и G 2 одинаковы.

Если вершины {V 1 , V 2 , .. Vk} образуют цикл длины K в G 1 , то вершины {f (V 1 ), f (V 2 ),… f (Vk)} должны образовывать цикл длины K в G 2 .

Все перечисленные выше условия необходимы для изоморфности графов G 1 и G 2 , но недостаточны для доказательства изоморфности графов.

  • (G 1 ≡ G 2 ) тогда и только тогда, когда (G 1 - ≡ G 2 -), где G 1 и G 2 - простые графы.

  • (G 1 ≡ G 2 ), если матрицы смежности G 1 и G 2 совпадают.

  • (G 1 ≡ G 2 ) тогда и только тогда, когда соответствующие подграфы G 1 и G 2 (полученные удалением некоторых вершин в G1 и их образов в графе G 2 ) изоморфны.

Example

Какие из следующих графов изоморфны?

В графе G 3 вершина w имеет только степень 3, тогда как все остальные вершины графа имеют степень 2. Следовательно, G3 не изоморфна G 1 или G 2 .

Взяв дополнения к G 1 и G 2 , вы получите -

Здесь (G 1 - ≡ G 2 -), следовательно (G 1 ≡ G 2 ).

Планарные графики

Граф 'G' называется плоским, если его можно нарисовать на плоскости или сфере так, чтобы никакие два ребра не пересекались друг с другом в не вершинной точке.

Example

Регионы

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

Example

Степень ограниченного региона r = deg(r) = Количество ребер, охватывающих области r.

deg(1) = 3
deg(2) = 4
deg(3) = 4

deg(4) = 3
deg(5) = 8

Степень неограниченного региона r = deg(r) = Количество ребер, охватывающих области r.

deg(R1) = 4
deg(R2) = 6

В планарных графах сохраняются следующие свойства:

В плоском графе с n вершинами сумма степеней всех вершин равна -

n Σ i = 1 град (V i ) = 2 | E |

В соответствии с Sum of Degrees of Regions/ Теорема, в плоском графе с n областями сумма степеней областей -

n Σ i = 1 deg (ri) = 2 | E |

Основываясь на приведенной выше теореме, вы можете сделать следующие выводы -

В плоском графе

Если степень каждой области равна K, то сумма степеней областей равна -

K | R | = 2 | E |

Если степень каждой области не меньше K (≥ K), то

K | R | ≤ 2 | E |

Если степень каждой области не превышает K (≤ K), то

K | R | ≥ 2 | E |

Note - Предположим, что у всех регионов одинаковая степень.

В соответствии с Euler’s Formulae на плоских графах,

Если граф G является связным плоским, то

| V | + | R | = | E | + 2

Если планарный граф с K-компонентами, то

| V | + | R | = | E | + (К + 1)

Где, | V | - количество вершин, | E | - количество ребер, а | R | - количество регионов.

Неравенство вершин края

Если G является связным плоским графом со степенью каждой области не менее K, то

| E | ≤ k / (k-2) {| v | - 2}

Вы знаете, | V | + | R | = | E | + 2

K. | R | ≤ 2 | E |

K (| E | - | V | + 2) ≤ 2 | E |

(K - 2) | E | ≤ К (| V | - 2)

| E | ≤ k / (k-2) {| v | - 2}

Если G - простой связный планарный граф, то

|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4

Существует хотя бы одна вершина V • ∈ G такая, что deg (V) ≤ 5.

Если 'G' - простой связный плоский граф (как минимум с двумя ребрами) и без треугольников, то

|E| ≤ {2|V| – 4}

Теорема Куратовского

Граф 'G' непланарен тогда и только тогда, когда 'G' имеет подграф, гомеоморфный K 5 или K 3,3 .

Гомоморфизм

Два графа G 1 и G 2 называются гомоморфными, если каждый из этих графов может быть получен из одного и того же графа 'G', разделив некоторые ребра графа G на большее количество вершин. Взгляните на следующий пример -

Разделите ребро rs на два ребра, добавив одну вершину.

Графики, показанные ниже, гомоморфны первому графу.

Если G 1 изоморфен G 2 , то G гомеоморфен G 2 , но обратное не обязательно.

  • Любой граф с 4 или менее вершинами планарен.

  • Любой граф с 8 или менее ребрами является плоским.

  • Полный граф K n планарен тогда и только тогда, когда n ≤ 4.

  • Полный двудольный граф K m, n является плоским тогда и только тогда, когда m ≤ 2 или n ≤ 2.

  • Простой неплоский граф с минимальным числом вершин - это полный граф K 5 .

  • Простой неплоский граф с минимальным числом ребер - это K 3, 3 .

Многогранный граф

Простой связный плоский граф называется многогранным графом, если степень каждой вершины ≥ 3, т. Е. Deg (V) ≥ 3 ∀ V ∈ G.

  • 3 | V | ≤ 2 | E |

  • 3 | R | ≤ 2 | E |