Théorie des graphes - Isomorphisme

Un graphe peut exister sous différentes formes ayant le même nombre de sommets, d'arêtes et également la même connectivité d'arêtes. Ces graphes sont appelés graphes isomorphes. Notez que nous étiquetons les graphiques dans ce chapitre principalement dans le but de s'y référer et de les reconnaître les uns des autres.

Graphiques isomorphes

Deux graphes G 1 et G 2 sont dits isomorphes si -

  • Leur nombre de composants (sommets et arêtes) est le même.

  • Leur connectivité de périphérie est conservée.

Note- En bref, sur les deux graphes isomorphes, l'un est une version modifiée de l'autre. Un graphe non étiqueté peut également être considéré comme un graphe isomorphe.

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

Si G 1 ≡ G 2 alors -

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

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

Les séquences de degrés de G 1 et G 2 sont identiques.

Si les sommets {V 1 , V 2 , .. Vk} forment un cycle de longueur K dans G 1 , alors les sommets {f (V 1 ), f (V 2 ),… f (Vk)} devraient former un cycle de longueur K en G 2 .

Toutes les conditions ci-dessus sont nécessaires pour que les graphes G 1 et G 2 soient isomorphes, mais pas suffisantes pour prouver que les graphes sont isomorphes.

  • (G 1 ≡ G 2 ) si et seulement si (G 1 - ≡ G 2 -) où G 1 et G 2 sont des graphes simples.

  • (G 1 ≡ G 2 ) si les matrices d'adjacence de G 1 et G 2 sont identiques.

  • (G 1 ≡ G 2 ) si et seulement si les sous-graphes correspondants de G 1 et G 2 (obtenus en supprimant certains sommets de G1 et leurs images dans le graphe G 2 ) sont isomorphes.

Example

Lequel des graphiques suivants est isomorphe?

Dans le graphe G 3 , le sommet 'w' n'a que le degré 3, alors que tous les autres sommets du graphe ont le degré 2. Donc G3 n'est pas isomorphe à G 1 ou G 2 .

En prenant des compléments de G 1 et G 2 , vous avez -

Ici, (G 1 - ≡ G 2 -), d'où (G 1 ≡ G 2 ).

Graphiques planaires

Un graphe «G» est dit plan s'il peut être dessiné sur un plan ou une sphère de sorte qu'aucune arête ne se croise en un point non-sommet.

Example

Régions

Chaque graphe plan divise le plan en zones connectées appelées régions.

Example

Degré d'une région délimitée r = deg(r) = Nombre d'arêtes entourant les régions r.

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

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

Degré d'une région illimitée r = deg(r) = Nombre d'arêtes entourant les régions r.

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

Dans les graphes planaires, les propriétés suivantes sont bonnes -

Dans un graphe planaire avec 'n' sommets, la somme des degrés de tous les sommets est -

n Σ i = 1 degré (V i ) = 2 | E |

Selon Sum of Degrees of Regions/ Théorème, dans un graphe planaire avec 'n' régions, la somme des degrés des régions est -

n Σ i = 1 degré (ri) = 2 | E |

Sur la base du théorème ci-dessus, vous pouvez tirer les conclusions suivantes -

Dans un graphe planaire,

Si le degré de chaque région est K, alors la somme des degrés des régions est -

K | R | = 2 | E |

Si le degré de chaque région est au moins K (≥ K), alors

K | R | ≤ 2 | E |

Si le degré de chaque région est au plus K (≤ K), alors

K | R | ≥ 2 | E |

Note - Supposons que toutes les régions aient le même degré.

Selon Euler’s Formulae sur des graphes planaires,

Si un graphe 'G' est un plan connexe, alors

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

Si un graphe planaire avec des composants 'K', alors

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

Où, | V | est le nombre de sommets, | E | est le nombre d'arêtes, et | R | est le nombre de régions.

Inégalité de sommet de bord

Si 'G' est un graphe planaire connexe avec le degré de chaque région au moins 'K' alors,

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

Vous savez, | V | + | R | = | E | + 2

K. | R | ≤ 2 | E |

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

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

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

Si 'G' est un simple graphe planaire connecté, alors

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

Il existe au moins un sommet V • ∈ G, tel que deg (V) ≤ 5.

Si 'G' est un graphe planaire simple connecté (avec au moins 2 arêtes) et sans triangles, alors

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

Théorème de Kuratowski

Un graphe 'G' est non planaire si et seulement si 'G' a un sous-graphe homéomorphe à K 5 ou K 3,3 .

Homomorphisme

Deux graphes G 1 et G 2 sont dits homomorphes, si chacun de ces graphes peut être obtenu à partir du même graphe «G» en divisant certaines arêtes de G par plus de sommets. Jetez un œil à l'exemple suivant -

Divisez l'arête «rs» en deux arêtes en ajoutant un sommet.

Les graphiques ci-dessous sont homomorphes au premier graphique.

Si G 1 est isomorphe à G 2 , alors G est homéomorphe à G2 mais l'inverse n'a pas besoin d'être vrai.

  • Tout graphe avec 4 sommets ou moins est plan.

  • Tout graphe avec 8 arêtes ou moins est plan.

  • Un graphe complet K n est plan si et seulement si n ≤ 4.

  • Le graphe biparti complet K m, n est plan si et seulement si m ≤ 2 ou n ≤ 2.

  • Un graphe non planaire simple avec un nombre minimum de sommets est le graphe complet K 5 .

  • Le graphe non planaire simple avec un nombre minimum d'arêtes est K 3, 3 .

Graphe polyédrique

Un graphe planaire connexe simple est appelé graphe polyédrique si le degré de chaque sommet est ≥ 3, c'est-à-dire deg (V) ≥ 3 ∀ V ∈ G.

  • 3 | V | ≤ 2 | E |

  • 3 | R | ≤ 2 | E |