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

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

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

Два графа G ₁ и G ₂ называются изоморфными, если —

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

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

There exists a function ‘f’ from vertices of G 1 to vertices of G 2
   [f: V(G 1 ) ⇒ V(G 2 )], 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} ∈ G 1 , then the 
   edge {f(U), f(V)} ∈ G 2 , then G 1 ≡ G 2 .

Заметка

Если G ₁ ≡ G _2, то —

• | V (G ₁ ) | = | V (G ₂ ) |

• | E (G ₁ ) | = | E (G ₂ ) |

• Степени последовательности G ₁ и G ₂ одинаковы.

• Если вершины {V ₁ , V ₂ , .. V _k } образуют цикл длины K в G ₁ , то вершины {f (V ₁ ), f (V ₂ ),… f (V _k )} должны сформироваться цикл длины K в G ₂ .

| V (G ₁ ) | = | V (G ₂ ) |

| E (G ₁ ) | = | E (G ₂ ) |

Степени последовательности G ₁ и G ₂ одинаковы.

Если вершины {V ₁ , V ₂ , .. V _k } образуют цикл длины K в G ₁ , то вершины {f (V ₁ ), f (V ₂ ),… f (V _k )} должны сформироваться цикл длины K в G ₂ .

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

• (G ₁ ≡ G ₂ ) тогда и только тогда, когда ( G ₁ — ≡ G ₂ — ), где G ₁ и G ₂ — простые графы.

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

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

(G ₁ ≡ G ₂ ) тогда и только тогда, когда ( G ₁ — ≡ G ₂ — ), где G ₁ и G ₂ — простые графы.

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

(G ₁ ≡ G ₂ ) тогда и только тогда, когда соответствующие подграфы G ₁ и G ₂ (полученные путем удаления некоторых вершин в G ₁ и их изображений в графе G ₂ ) изоморфны.

пример

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

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

Принимая дополнения G ₁ и G ₂ , у вас есть —

Здесь ( G ₁ — ≡ G ₂ — ), следовательно, (G ₁ ≡ G ₂ ).

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

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

пример

районы

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

пример

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

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

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

deg(R 1 ) = 4
deg(R 2 ) = 6

На плоских графиках действуют следующие свойства:

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

  n ∑ i = 1 градус (V _i ) = 2 | E |

• 2. Согласно теореме о сумме степеней областей , в плоском графе с ‘n’ областями сумма степеней областей равна —

  n ∑ i = 1 градус (r _i ) = 2 | E |

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

2. Согласно теореме о сумме степеней областей , в плоском графе с ‘n’ областями сумма степеней областей равна —

На основании приведенной выше теоремы можно сделать следующие выводы:

На плоском графике

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

  K | R | = 2 | E |

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

  K | R | ≤ 2 | E |

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

  K | R | ≥ 2 | E |

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

K | R | = 2 | E |

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

K | R | ≤ 2 | E |

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

K | R | ≥ 2 | E |

Примечание. Предположим, что все регионы имеют одинаковую степень.

3. Согласно формулам Эйлера на плоских графах,

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

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

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

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

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

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

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

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

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

4. Краевое неравенство вершин

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

| E | ≤ k / k — 2 {| v | — 2}

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

K. | R | ≤ 2 | E |

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

(К — 2) | Е | ≤ K (| V | — 2)

| E | ≤ k / k — 2 {| v | — 2}

5. Если ‘G’ — простой связный плоский граф, то

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

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

6. Если ‘G’ — простой связный плоский граф (по крайней мере с 2 ребрами) и без треугольников, то

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

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

Граф «G» неплоский в том и только в том случае, если у «G» есть подграф, гомеоморфный K ₅ или K _3,3 .

Гомоморфизм

Два графа G ₁ и G ₂ называются гомоморфными, если каждый из этих графов можно получить из одного и того же графа ‘G’, разделив некоторые ребра графа G на большее число вершин. Взгляните на следующий пример —

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

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

Если G ₁ изоморфна G ₂ , то G гомеоморфна G _2, но обратное не обязательно верно.

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

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

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

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

• Простой непланарный граф с минимальным числом вершин является полным графом K ₅ .

• Простой непланарный граф с минимальным числом ребер равен K _{3, 3} .

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

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

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

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

Простой непланарный граф с минимальным числом вершин является полным графом K ₅ .

Простой непланарный граф с минимальным числом ребер равен K _{3, 3} .

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

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