Teoria dei grafi - Isomorfismo

Un grafo può esistere in forme diverse con lo stesso numero di vertici, bordi e anche la stessa connettività dei bordi. Tali grafici sono chiamati grafici isomorfi. Notare che etichettiamo i grafici in questo capitolo principalmente allo scopo di farvi riferimento e riconoscerli l'uno dall'altro.

Grafici isomorfi

Due grafici G 1 e G 2 si dicono isomorfi se -

  • Il loro numero di componenti (vertici e bordi) è lo stesso.

  • La loro connettività edge viene mantenuta.

Note- In breve, dei due grafici isomorfi, uno è una versione ottimizzata dell'altro. Un grafico senza etichetta può anche essere pensato come un grafico isomorfo.

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

Se G 1 ≡ G 2 allora -

| V (Sol 1 ) | = | V (SOL 2 ) |

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

Le sequenze di gradi di G 1 e G 2 sono le stesse.

Se i vertici {V 1 , V 2 , .. Vk} formano un ciclo di lunghezza K in G 1 , allora i vertici {f (V 1 ), f (V 2 ),… f (Vk)} dovrebbero formare un ciclo di lunghezza K in G 2 .

Tutte le condizioni di cui sopra sono necessarie affinché i grafici G 1 e G 2 siano isomorfi, ma non sufficienti per dimostrare che i grafici sono isomorfi.

  • (G 1 ≡ G 2 ) se e solo se (G 1 - ≡ G 2 -) dove G 1 e G 2 sono grafici semplici.

  • (G 1 ≡ G 2 ) se le matrici di adiacenza di G 1 e G 2 sono uguali.

  • (G 1 ≡ G 2 ) se e solo se i corrispondenti sottografi di G 1 e G 2 (ottenuti cancellando alcuni vertici in G1 e le loro immagini nel grafo G 2 ) sono isomorfi.

Example

Quale dei seguenti grafici è isomorfo?

Nel grafo G 3 , il vertice "w" ha solo grado 3, mentre tutti gli altri vertici del grafo hanno grado 2. Quindi G3 non è isomorfo a G 1 o G 2 .

Prendendo i complementi di G 1 e G 2 , hai:

Qui, (G 1 - ≡ G 2 -), quindi (G 1 ≡ G 2 ).

Grafici planari

Un grafico "G" si dice planare se può essere disegnato su un piano o una sfera in modo che non ci siano due bordi che si incrociano in un punto non vertice.

Example

Regioni

Ogni grafico planare divide il piano in aree collegate chiamate regioni.

Example

Grado di una regione delimitata r = deg(r) = Numero di bordi che racchiudono le regioni r.

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

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

Grado di una regione illimitata r = deg(r) = Numero di bordi che racchiudono le regioni r.

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

Nei grafici planari, le seguenti proprietà sono valide:

In un grafo planare con 'n' vertici, la somma dei gradi di tutti i vertici è -

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

Secondo Sum of Degrees of Regions/ Teorema, in un grafo planare con 'n' regioni, la somma dei gradi delle regioni è -

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

Sulla base del teorema di cui sopra, puoi trarre le seguenti conclusioni:

In un grafo planare,

Se il grado di ciascuna regione è K, la somma dei gradi delle regioni è -

K | R | = 2 | E |

Se il grado di ciascuna regione è almeno K (≥ K), allora

K | R | ≤ 2 | E |

Se il grado di ciascuna regione è al massimo K (≤ K), allora

K | R | ≥ 2 | E |

Note - Supponiamo che tutte le regioni abbiano lo stesso grado.

Secondo Euler’s Formulae su grafici planari,

Se un grafo 'G' è un planare connesso, allora

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

Se un grafico planare con componenti "K", allora

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

Dove, | V | è il numero di vertici, | E | è il numero di archi e | R | è il numero di regioni.

Disuguaglianza del vertice del bordo

Se 'G' è un grafo planare connesso con il grado di ciascuna regione almeno 'K', allora,

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

Sai, | 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}

Se 'G' è un semplice grafo planare connesso, allora

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

Esiste almeno un vertice V • ∈ G, tale che deg (V) ≤ 5.

Se 'G' è un semplice grafo planare connesso (con almeno 2 bordi) e senza triangoli, allora

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

Teorema di Kuratowski

Un grafo "G" è non planare se e solo se "G" ha un sottografo omeomorfo a K 5 o K 3,3 .

Omomorfismo

Si dice che due grafi G 1 e G 2 siano omomorfi, se ciascuno di questi grafi può essere ottenuto dallo stesso grafo 'G' dividendo alcuni spigoli di G con più vertici. Dai un'occhiata al seguente esempio:

Dividi il bordo "rs" in due bordi aggiungendo un vertice.

I grafici mostrati di seguito sono omomorfi al primo grafico.

Se G 1 è isomorfo a G 2 , allora G è omeomorfo a G2 ma non è necessario che sia vero il contrario.

  • Qualsiasi grafo con 4 o meno vertici è planare.

  • Qualsiasi grafico con 8 o meno spigoli è planare.

  • Un grafo completo K n è planare se e solo se n ≤ 4.

  • Il grafo bipartito completo K m, n è planare se e solo se m ≤ 2 oppure n ≤ 2.

  • Un semplice grafo non planare con un numero minimo di vertici è il grafo completo K 5 .

  • Il grafo semplice non planare con un numero minimo di spigoli è K 3, 3 .

Grafico poliedrico

Un grafo planare connesso semplice è chiamato grafo poliedrico se il grado di ciascun vertice è ≥ 3, cioè deg (V) ≥ 3 ∀ V ∈ G.

  • 3 | V | ≤ 2 | E |

  • 3 | R | ≤ 2 | E |