Teoria dei grafi - Tipi di grafici

Esistono vari tipi di grafici a seconda del numero di vertici, del numero di bordi, dell'interconnettività e della loro struttura complessiva. In questo capitolo discuteremo solo alcuni importanti tipi di grafici.

Grafico nullo

A graph having no edges è chiamato un grafico nullo.

Esempio

Nel grafico sopra, ci sono tre vertici denominati "a", "b" e "c", ma non ci sono bordi tra di loro. Quindi è un grafico nullo.

Grafico banale

UN graph with only one vertex è chiamato Trivial Graph.

Esempio

Nel grafico mostrato sopra, c'è solo un vertice "a" senza altri bordi. Quindi è un grafico banale.

Grafico non orientato

Un grafo non diretto contiene bordi ma i bordi non sono quelli diretti.

Esempio

In questo grafico, "a", "b", "c", "d", "e", "f", "g" sono i vertici e "ab", "bc", "cd", "da ',' ag ',' gf ',' ef 'sono i bordi del grafico. Poiché si tratta di un grafico non orientato, i bordi "ab" e "ba" sono gli stessi. Allo stesso modo anche altri bordi considerati allo stesso modo.

Grafico diretto

In un grafico orientato, ogni bordo ha una direzione.

Esempio

Nel grafico sopra, abbiamo sette vertici "a", "b", "c", "d", "e", "f" e "g" e otto spigoli "ab", "cb", " dc "," ad "," ec "," fe "," gf "e" ga ". Trattandosi di un grafico orientato, ogni bordo reca una freccia che ne mostra la direzione. Notare che in un grafo orientato, "ab" è diverso da "ba".

Grafico semplice

Un grafico with no loops e no parallel edges è chiamato un semplice grafico.

• Il numero massimo di archi possibile in un singolo grafo con 'n' vertici è ⁿ C ₂ dove ⁿ C ₂ = n (n - 1) / 2.

• Il numero di grafi semplici possibili con 'n' vertici = 2 _{ⁿ c 2} = 2 ^{n (n-1) / 2} .

Esempio

Nel grafico seguente, ci sono 3 vertici con 3 bordi che è il massimo escludendo i bordi paralleli e gli anelli. Ciò può essere dimostrato utilizzando le formule di cui sopra.

Il numero massimo di archi con n = 3 vertici -

ⁿ C ₂ = n (n – 1) / 2

= 3 (3–1) / 2

= 6/2

= 3 bordi

Il numero massimo di grafici semplici con n = 3 vertici -

2 _{ⁿ C 2} = 2 ^{n (n-1) / 2}

= 2 ^{3 (3-1) / 2}

= 2 ³

8

Questi 8 grafici sono come mostrato di seguito:

Grafico connesso

Si dice che un grafo G sia connesso if there exists a path between every pair of vertices. Dovrebbe esserci almeno un bordo per ogni vertice nel grafico. Quindi possiamo dire che è collegato a qualche altro vertice sull'altro lato del bordo.

Esempio

Nel grafico seguente, ogni vertice ha il proprio bordo connesso all'altro bordo. Quindi è un grafico connesso.

Grafico disconnesso

Un grafo G è disconnesso, se non contiene almeno due vertici collegati.

Esempio 1

Il grafico seguente è un esempio di un grafico disconnesso, in cui sono presenti due componenti, uno con vertici 'a', 'b', 'c', 'd' e un altro con 'e', ​​'f', 'g', vertici 'h'.

I due componenti sono indipendenti e non collegati tra loro. Quindi è chiamato grafico disconnesso.

Esempio 2

In questo esempio, ci sono due componenti indipendenti, abfe e cd, che non sono collegati tra loro. Quindi questo è un grafico disconnesso.

Grafico regolare

Si dice che un grafico G sia regolare, if all its vertices have the same degree. In un grafico, se il grado di ciascun vertice è "k", il grafico viene chiamato "grafo k-regolare".

Esempio

Nei grafici seguenti, tutti i vertici hanno lo stesso grado. Quindi questi grafici sono chiamati grafici regolari.

In entrambi i grafici, tutti i vertici hanno grado 2. Sono chiamati 2-Regular Graphs.

Grafico completo

Un semplice grafo con 'n' vertici reciproci è chiamato grafo completo e lo è denoted by ‘K_n’. Nel grafico,a vertex should have edges with all other vertices, quindi ha chiamato un grafico completo.

In altre parole, se un vertice è connesso a tutti gli altri vertici in un grafo, allora viene chiamato grafo completo.

Esempio

Nei grafici seguenti, ogni vertice del grafo è connesso a tutti i rimanenti vertici del grafo tranne che da solo.

Nel grafico I,

	un	b	c
un	Non collegata	Collegato	Collegato
b	Collegato	Non collegata	Collegato
c	Collegato	Collegato	Non collegata

Nel grafico II,

	p	q	r	S
p	Non collegata	Collegato	Collegato	Collegato
q	Collegato	Non collegata	Collegato	Collegato
r	Collegato	Collegato	Non collegata	Collegato
S	Collegato	Collegato	Collegato	Non collegata

Grafico del ciclo

Un grafo semplice con vertici "n" (n> = 3) e archi "n" è chiamato grafo a ciclo se tutti i suoi archi formano un ciclo di lunghezza "n".

Se il grado di ciascun vertice nel grafico è due, viene chiamato grafico del ciclo.

Notation- C _n

Esempio

Dai un'occhiata ai seguenti grafici:

• Il grafico I ha 3 vertici con 3 bordi che formano un ciclo "ab-bc-ca".

• Il grafico II ha 4 vertici con 4 bordi che formano un ciclo 'pq-qs-sr-rp'.

• Il grafico III ha 5 vertici con 5 bordi che formano un ciclo "ik-km-ml-lj-ji".

Quindi tutti i grafici dati sono grafici di ciclo.

Grafico ruota

Un grafico della ruota è ottenuto da un grafico del ciclo C _n-1 aggiungendo un nuovo vertice. Quel nuovo vertice è chiamato aHubche è connesso a tutti i vertici di C _n .

Notazione - W _n

N. di spigoli in W _n = N. di spigoli dal mozzo a tutti gli altri vertici +

Numero di bordi da tutti gli altri nodi nel grafico del ciclo senza hub.

= (n – 1) + (n – 1)

= 2 (n – 1)

Esempio

Dai un'occhiata ai grafici seguenti. Sono tutti grafici delle ruote.

Nel grafico I, si ottiene da C ₃ aggiungendo un vertice al centro denominato "d". È indicato come W ₄ .

Numero di bordi in W4 = 2 (n-1) = 2 (3) = 6

Nel grafico II, si ottiene da C4 aggiungendo un vertice al centro denominato "t". È indicato come W ₅ .

Numero di spigoli in W5 = 2 (n-1) = 2 (4) = 8

Nel grafico III, si ottiene da C ₆ aggiungendo un vertice al centro denominato "o". È indicato come W ₇ .

Numero di bordi in W4 = 2 (n-1) = 2 (6) = 12

Grafico ciclico

Un grafico with at least one ciclo è chiamato un grafico ciclico.

Esempio

Nel grafico di esempio sopra, abbiamo due cicli abcda e cfgec. Quindi è chiamato un grafico ciclico.

Grafico aciclico

Un grafico with no cycles è chiamato grafo aciclico.

Esempio

Nel grafico di esempio sopra, non abbiamo cicli. Quindi è un grafico non ciclico.

Grafico bipartito

Un semplice grafo G = (V, E) con partizione di vertice V = {V ₁ , V ₂ } è chiamato grafo bipartitoif every edge of E joins a vertex in V1 to a vertex in V₂.

In generale, un grafo Bipertite ha due insiemi di vertici, diciamo V1 e V2, e se viene disegnato un bordo, dovrebbe connettere qualsiasi vertice nell'insieme V ₁ a qualsiasi vertice nell'insieme V ₂ .

Esempio

In questo grafico, puoi osservare due insiemi di vertici: V ₁ e V ₂ . Qui, due archi denominati "ae" e "bd" collegano i vertici di due insiemi V ₁ e V ₂ .

Grafico bipartito completo

Un grafo bipartito 'G', G = (V, E) con partizione V = {V ₁ , V ₂ } si dice che sia un grafo bipartito completo se ogni vertice in V ₁ è connesso a ogni vertice di V ₂ .

In generale, un grafo bipartito completo collega ogni vertice dell'insieme V ₁ a ciascun vertice dell'insieme V ₂ .

Esempio

Il seguente grafico è un grafo bipartito completo perché ha archi che collegano ogni vertice dell'insieme V ₁ a ciascun vertice dell'insieme V ₂ .

Se | V ₁ | = me | V ₂ | = n, allora il grafo bipartito completo è indicato con K _{m, n} .

• K _{m, n} ha (m + n) vertici e (mn) bordi.
• K _{m, n} è un grafo regolare se m = n.

In generale, a complete bipartite graph is not a complete graph.

K _{m, n} è un grafico completo se m = n = 1.

Il numero massimo di archi in un grafo bipartito con n vertici è -

[n ² /4]

Se n = 10, k5, 5 = [n2 / 4] = [10 ² /4] = 25.

Allo stesso modo, K6, 4 = 24

K7, 3 = 21

K8, 2 = 16

K9, 1 = 9

Se n = 9, k5, 4 = [n2 / 4] = [92/4] = 20

Allo stesso modo, K6, 3 = 18

K7, 2 = 14

K8, 1 = 8

"G" è un grafo bipartito se "G" non ha cicli di lunghezza dispari. Un caso speciale di grafo bipartito è un grafo a stella.

Grafico a stella

Un grafo bipartito completo della forma K1, n-1 è un grafo stellare con n vertici. Un grafo a stella è un grafo bipartito completo se un singolo vertice appartiene a un insieme e tutti i vertici rimanenti appartengono all'altro insieme.

Esempio

Nei grafici precedenti, su "n" vertici, tutti i vertici "n – 1" sono collegati a un singolo vertice. Quindi è nella forma di K ¹ , ^n-1 che sono grafici stellari.

Complemento di un grafico

Sia 'G−' un grafo semplice con alcuni vertici come quello di 'G' e uno spigolo {U, V} è presente in 'G−', se lo spigolo non è presente in G. Significa che due vertici sono adiacenti in 'G−' se i due vertici non sono adiacenti in G.

Se gli archi che esistono nel grafico I sono assenti in un altro grafico II, e se sia il grafico I che il grafico II sono combinati insieme per formare un grafico completo, allora il grafico I e il grafico II sono chiamati complementi l'uno dell'altro.

Esempio

Nell'esempio seguente, graph-I ha due bordi "cd" e "bd". Il suo grafo del complemento-II ha quattro bordi.

Si noti che gli archi nel grafo-I non sono presenti nel grafo-II e viceversa. Quindi, la combinazione di entrambi i grafici fornisce un grafo completo di "n" vertici.

Note - Una combinazione di due grafici complementari fornisce un grafico completo.

Se "G" è un grafico semplice, allora

| E (G) | + | E ('G -') | = | E (Kn) |, dove n = numero di vertici nel grafo.

Esempio

Sia "G" un grafo semplice con nove vertici e dodici archi, trova il numero di archi in "G-".

Hai, | E (G) | + | E ('G -') | = | E (Kn) |

12 + | E ('Sol -') | =

9 (9-1) / 2 = ⁹ C ₂

12 + | E ('Sol -') | = 36

| E ('G -') | = 24

"G" è un grafico semplice con 40 archi e il suo complemento "G−" ha 38 archi. Trova il numero di vertici nel grafo G o 'G−'.

Lascia che il numero di vertici nel grafo sia "n".

Abbiamo, | E (G) | + | E ('G -') | = | E (Kn) |

40 + 38 = n (n-1) / 2

156 = n (n-1)

13 (12) = n (n-1)

n = 13