Teoria dei grafi - Guida rapida

Nel dominio della matematica e dell'informatica, la teoria dei grafi è lo studio dei grafi che riguarda la relazione tra archi e vertici . È un argomento popolare che ha le sue applicazioni in informatica, tecnologia dell'informazione, bioscienze, matematica e linguistica per citarne alcuni. Senza ulteriori indugi, iniziamo con la definizione di un grafico.

Cos'è un grafico?

Un grafico è una rappresentazione pittorica di un insieme di oggetti in cui alcune coppie di oggetti sono collegate da collegamenti. Gli oggetti interconnessi sono rappresentati da punti denominati comeverticese vengono chiamati i collegamenti che collegano i vertici edges.

Formalmente, un grafico è una coppia di insiemi (V, E), dove Vè l'insieme dei vertici ed E è l'insieme degli archi, che collega le coppie di vertici. Dai un'occhiata al grafico seguente:

Nel grafico sopra,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Applicazioni della teoria dei grafi

La teoria dei grafi ha le sue applicazioni in diversi campi dell'ingegneria:

Electrical Engineering- I concetti della teoria dei grafi sono ampiamente utilizzati nella progettazione delle connessioni dei circuiti. I tipi o l'organizzazione delle connessioni sono denominati topologie. Alcuni esempi di topologie sono topologie a stella, bridge, serie e parallela.

Computer Science- La teoria dei grafi viene utilizzata per lo studio degli algoritmi. Per esempio,

  • Algoritmo di Kruskal
  • Algoritmo di Prim
  • Algoritmo di Dijkstra

Computer Network - Le relazioni tra i computer interconnessi nella rete seguono i principi della teoria dei grafi.

Science - La struttura molecolare e chimica di una sostanza, la struttura del DNA di un organismo, ecc. Sono rappresentate da grafici.

Linguistics - L'albero di analisi di una lingua e la grammatica di una lingua utilizzano grafici.

General- I percorsi tra le città possono essere rappresentati utilizzando grafici. La rappresentazione di informazioni ordinate gerarchicamente come l'albero genealogico può essere utilizzata come un tipo speciale di grafico chiamato albero.

Un grafico è un diagramma di punti e linee collegati ai punti. Ha almeno una linea che unisce un insieme di due vertici senza vertici che si connettono. Il concetto di grafi nella teoria dei grafi si basa su alcuni termini di base come punto, linea, vertice, bordo, grado di vertici, proprietà dei grafi, ecc. Qui, in questo capitolo, tratteremo questi fondamenti della teoria dei grafi.

Punto

A pointè una posizione particolare in uno spazio unidimensionale, bidimensionale o tridimensionale. Per una migliore comprensione, un punto può essere indicato da un alfabeto. Può essere rappresentato con un punto.

Esempio

Qui, il punto è un punto chiamato "a".

Linea

UN Lineè una connessione tra due punti. Può essere rappresentato con una linea continua.

Example

Qui, "a" e "b" sono i punti. Il collegamento tra questi due punti è chiamato linea.

Vertice

Un vertice è un punto in cui si incontrano più linee. È anche chiamato anode. Analogamente ai punti, anche un vertice è indicato da un alfabeto.

Example

Qui, il vertice è denominato con un alfabeto "a".

Bordo

Un bordo è il termine matematico per una linea che collega due vertici. Molti bordi possono essere formati da un singolo vertice. Senza un vertice, un bordo non può essere formato. Deve esserci un vertice iniziale e un vertice finale per un bordo.

Example

Qui, "a" e "b" sono i due vertici e il collegamento tra di loro è chiamato bordo.

Grafico

Un grafo 'G' è definito come G = (V, E) dove V è un insieme di tutti i vertici ed E è un insieme di tutti gli archi nel grafico.

Example 1

Nell'esempio sopra, ab, ac, cd e bd sono i bordi del grafico. Allo stesso modo, a, b, c e d sono i vertici del grafo.

Example 2

In questo grafico, ci sono quattro vertici a, b, c, e d e quattro bordi ab, ac, ad e cd.

Ciclo continuo

In un grafico, se un bordo viene disegnato dal vertice a se stesso, viene chiamato loop.

Example 1

Nel grafico sopra, V è un vertice per il quale ha un bordo (V, V) che forma un anello.

Example 2

In questo grafico, ci sono due anelli che si formano al vertice a e al vertice b.

Grado di vertice

È il numero di vertici adiacenti a un vertice V.

Notation - gradi (V).

In un grafo semplice con n numero di vertici, il grado di ogni vertice è -

deg (v) ≤ n - 1 ∀ v ∈ G

Un vertice può formare un bordo con tutti gli altri vertici tranne che da solo. Quindi il grado di un vertice sarà fino anumber of vertices in the graph minus 1. Questo 1 è per l'auto-vertice in quanto non può formare un ciclo da solo. Se è presente un ciclo in uno qualsiasi dei vertici, non è un grafico semplice.

Il grado di vertice può essere considerato in due casi di grafici:

  • Grafico non diretto

  • Grafico diretto

Grado di vertice in un grafico non orientato

Un grafo non orientato non ha bordi diretti. Considera i seguenti esempi.

Example 1

Dai un'occhiata al grafico seguente:

Nel grafico non orientato sopra,

  • deg (a) = 2, poiché ci sono 2 archi che si incontrano al vertice 'a'.

  • deg (b) = 3, poiché ci sono 3 archi che si incontrano al vertice 'b'.

  • deg (c) = 1, in quanto vi è 1 bordo formato al vertice 'c'

  • Quindi "c" è un file pendent vertex.

  • deg (d) = 2, poiché ci sono 2 archi che si incontrano al vertice 'd'.

  • deg (e) = 0, poiché ci sono 0 archi formati al vertice 'e'.

  • Quindi "e" è un file isolated vertex.

Example 2

Dai un'occhiata al grafico seguente:

Nel grafico sopra,

deg (a) = 2, deg (b) = 2, deg (c) = 2, deg (d) = 2 e deg (e) = 0.

Il vertice "e" è un vertice isolato. Il grafico non ha vertici pendenti.

Grado di vertice in un grafico orientato

In un grafo diretto, ogni vertice ha un'estensione indegree e un outdegree.

Indegree of a Graph

  • L'indice del vertice V è il numero di bordi che entrano nel vertice V.

  • Notation - deg− (V).

Fuori grado di un grafico

  • Fuori grado del vertice V è il numero di archi che escono dal vertice V.

  • Notation - gradi + (V).

Considera i seguenti esempi.

Example 1

Dai un'occhiata al seguente grafico diretto. Il vertice "a" ha due bordi, "ad" e "ab", che vanno verso l'esterno. Quindi il suo grado esterno è 2. Allo stesso modo, c'è un bordo "ga", che viene verso il vertice "a". Quindi l'indice di "a" è 1.

L'indegree e il outdegree degli altri vertici sono mostrati nella tabella seguente:

Vertice Indegree Outdegree
un 1 2
b 2 0
c 2 1
d 1 1
e 1 1
f 1 1
g 0 2

Example 2

Dai un'occhiata al seguente grafico diretto. Il vertice "a" ha un bordo "ae" che va verso l'esterno dal vertice "a". Quindi il suo grado esterno è 1. Allo stesso modo, il grafico ha un bordo "ba" che va verso il vertice "a". Quindi l'indice di "a" è 1.

L'indegree e il outdegree degli altri vertici sono mostrati nella tabella seguente:

Vertice Indegree Outdegree
un 1 1
b 0 2
c 2 0
d 1 1
e 1 1

Vertice pendente

Usando il grado di un vertice, abbiamo due tipi speciali di vertici. Un vertice di grado uno è chiamato vertice pendente.

Example

Qui, in questo esempio, il vertice "a" e il vertice "b" hanno un bordo connesso "ab". Quindi rispetto al vertice "a" c'è un solo spigolo verso il vertice "b" e analogamente rispetto al vertice "b" c'è un solo spigolo verso il vertice "a". Infine, il vertice "a" e il vertice "b" hanno un grado che è anche chiamato vertice pendente.

Vertice isolato

Un vertice con grado zero è chiamato vertice isolato.

Example

Qui, il vertice "a" e il vertice "b" non hanno connettività tra loro e anche con altri vertici. Quindi il grado di entrambi i vertici "a" e "b" è zero. Questi sono anche chiamati vertici isolati.

Adiacenza

Ecco le norme di adiacenza -

  • In un grafo, si dice che siano due vertici adjacent, se è presente un bordo tra i due vertici. Qui, l'adiacenza dei vertici è mantenuta dal singolo bordo che collega quei due vertici.

  • In un grafico, si dice che due bordi sono adiacenti, se c'è un vertice comune tra i due bordi. Qui, l'adiacenza degli spigoli è mantenuta dal singolo vertice che collega due spigoli.

Example 1

Nel grafico sopra -

  • 'a' e 'b' sono i vertici adiacenti, poiché tra di loro c'è un bordo comune 'ab'.

  • 'a' e 'd' sono i vertici adiacenti, poiché tra di loro c'è un bordo comune 'ad'.

  • ab 'e' be 'sono i bordi adiacenti, poiché tra loro c'è un vertice comune' b '.

  • be 'e' de 'sono gli spigoli adiacenti, poiché tra loro c'è un vertice comune' e '.

Example 2

Nel grafico sopra -

  • 'a' e 'd' sono i vertici adiacenti, poiché tra di loro c'è un bordo comune 'ad'.

  • "c" e "b" sono i vertici adiacenti, poiché tra loro c'è un bordo comune "cb".

  • "ad" e "cd" sono i bordi adiacenti, poiché tra di loro c'è un vertice comune "d".

  • "ac" e "cd" sono i bordi adiacenti, poiché tra di loro c'è un vertice comune "c".

Bordi paralleli

In un grafico, se una coppia di vertici è collegata da più di un bordo, questi sono chiamati bordi paralleli.

Nel grafico sopra, "a" e "b" sono i due vertici collegati tra loro da due spigoli "ab" e "ab". Quindi è chiamato come un bordo parallelo.

Multi grafico

Un grafico con bordi paralleli è noto come Multigraph.

Example 1

Nel grafico sopra, ci sono cinque bordi "ab", "ac", "cd", "cd" e "bd". Poiché "c" e "d" hanno due bordi paralleli tra loro, è un Multigraph.

Example 2

Nel grafico sopra, i vertici "b" e "c" hanno due bordi. Anche i vertici "e" e "d" hanno due bordi tra loro. Quindi è un Multigraph.

Sequenza dei gradi di un grafico

Se i gradi di tutti i vertici in un grafico sono disposti in ordine decrescente o crescente, la sequenza ottenuta è nota come sequenza di gradi del grafico.

Example 1

Vertice UN b c d e
Connessione a avanti Cristo anno Domini anno Domini c, b, e d
Grado 2 2 2 3 1

Nel grafico sopra, per i vertici {d, a, b, c, e}, la sequenza dei gradi è {3, 2, 2, 2, 1}.

Example 2

Vertice UN b c d e f
Connessione a essere corrente alternata b, d c, e anno Domini -
Grado 2 2 2 2 2 0

Nel grafico sopra, per i vertici {a, b, c, d, e, f}, la sequenza dei gradi è {2, 2, 2, 2, 2, 0}.

I grafici sono dotati di varie proprietà che vengono utilizzate per la caratterizzazione dei grafici a seconda delle loro strutture. Queste proprietà sono definite in termini specifici pertinenti al dominio della teoria dei grafi. In questo capitolo, discuteremo alcune proprietà di base comuni a tutti i grafici.

Distanza tra due vertici

È il numero di bordi in un percorso più breve tra il vertice U e il vertice V. Se sono presenti più percorsi che collegano due vertici, il percorso più breve è considerato come la distanza tra i due vertici.

Notazione - d (U, V)

Può essere presente un numero qualsiasi di percorsi da un vertice all'altro. Tra questi, devi scegliere solo quello più corto.

Example

Dai un'occhiata al grafico seguente:

Qui, la distanza dal vertice "d" al vertice "e" o semplicemente "de" è 1 poiché c'è un bordo tra di loro. Ci sono molti percorsi dal vertice 'd' al vertice 'e' -

  • da, ab, be
  • df, fg, ge
  • de (è considerato per la distanza tra i vertici)
  • df, fc, ca, ab, be
  • da, ac, cf, fg, ge

Eccentricità di un vertice

La distanza massima tra un vertice e tutti gli altri vertici è considerata come l'eccentricità del vertice.

Notazione - e (V)

Viene presa la distanza da un particolare vertice a tutti gli altri vertici nel grafico e tra quelle distanze, l'eccentricità è la più alta delle distanze.

Example

Nel grafico sopra, l'eccentricità di "a" è 3.

La distanza da "a" a "b" è 1 ("ab"),

da 'a' a 'c' è 1 ('ac'),

da "a" a "d" è 1 ("annuncio"),

da 'a' a 'e' è 2 ('ab' - 'be') o ('ad' - 'de'),

da 'a' a 'f' è 2 ('ac' - 'cf') o ('ad' - 'df'),

da 'a' a 'g' è 3 ('ac' - 'cf' - 'fg') o ('ad' - 'df' - 'fg').

Quindi l'eccentricità è 3, che è un massimo dal vertice "a" dalla distanza tra "ag" che è massimo.

In altre parole,

e (b) = 3

e (c) = 3

e (d) = 2

e (e) = 3

e (f) = 3

e (g) = 3

Raggio di un grafico connesso

L'eccentricità minima da tutti i vertici è considerata come il raggio del grafico G. La minima tra tutte le distanze massime tra un vertice e tutti gli altri vertici è considerata come il raggio del grafico G.

Notazione - r (G)

Da tutte le eccentricità dei vertici in un grafo, il raggio del grafo connesso è il minimo di tutte quelle eccentricità.

Example

Nel grafico sopra r (G) = 2, che è l'eccentricità minima per 'd'.

Diametro di un grafico

L'eccentricità massima da tutti i vertici è considerata come il diametro del grafico G. Il massimo tra tutte le distanze tra un vertice e tutti gli altri vertici è considerato come il diametro del grafico G.

Notation − d(G) - Da tutte le eccentricità dei vertici in un grafo, il diametro del grafo connesso è il massimo di tutte quelle eccentricità.

Example

Nel grafico sopra, d (G) = 3; che è la massima eccentricità.

Punto centrale

Se l'eccentricità di un grafico è uguale al suo raggio, allora è noto come il punto centrale del grafico. Se

e (V) = r (V),

quindi "V" è il punto centrale del grafico "G".

Example

Nel grafico di esempio, "d" è il punto centrale del grafico.

e (d) = r (d) = 2

Centro

L'insieme di tutti i punti centrali di "G" è chiamato il centro del grafico.

Example

Nel grafico di esempio, {'d'} è il centro del grafico.

Circonferenza

Il number of edges in the longest cycle of ‘G’ è chiamato come la circonferenza di 'G'.

Example

Nel grafico di esempio, la circonferenza è 6, che abbiamo derivato dal ciclo più lungo acfgeba o acfdeba.

Circonferenza

Il numero di bordi nel ciclo più breve di "G" è chiamato circonferenza.

Notation: g (G).

Example - Nel grafico di esempio, la circonferenza del grafico è 4, che abbiamo derivato dal ciclo più breve acfda o dfged o abeda.

Teorema della somma dei gradi dei vertici

Se G = (V, E) è un grafo non diretto con vertici V = {V 1 , V 2 ,… V n } allora

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

Corollary 1

Se G = (V, E) è un grafo orientato con vertici V = {V 1 , V 2 ,… V n }, allora

n Σ i = 1 deg + (V i ) = | E | = n Σ i = 1 deg− (V i )

Corollary 2

In qualsiasi grafo non diretto, il numero di vertici con grado dispari è pari.

Corollary 3

In un grafo non diretto, se il grado di ogni vertice è k, allora

k | V | = 2 | E |

Corollary 4

In un grafo non diretto, se il grado di ciascun vertice è almeno k, allora

k | V | ≤ 2 | E |

| Corollary 5

In un grafo non diretto, se il grado di ogni vertice è al massimo k, allora

k | V | ≥ 2 | E |

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 è n C 2 dove n C 2 = n (n - 1) / 2.

  • Il numero di grafi semplici possibili con 'n' vertici = 2 n 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 -

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

= 3 (3–1) / 2

= 6/2

= 3 bordi

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

2 n C 2 = 2 n (n-1) / 2

= 2 3 (3-1) / 2

= 2 3

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 ‘Kn. 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 3 aggiungendo un vertice al centro denominato "d". È indicato come W 4 .

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 5 .

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

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

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 1 , V 2 } è chiamato grafo bipartitoif every edge of E joins a vertex in V1 to a vertex in V2.

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 1 a qualsiasi vertice nell'insieme V 2 .

Esempio

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

Grafico bipartito completo

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

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

Esempio

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

Se | V 1 | = me | V 2 | = 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 2 /4]

Se n = 10, k5, 5 = [n2 / 4] = [10 2 /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 1 , 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 = 9 C 2

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

Gli alberi sono grafici che non contengono nemmeno un singolo ciclo. Rappresentano la struttura gerarchica in forma grafica. Gli alberi appartengono alla classe di grafici più semplice. Nonostante la loro semplicità, hanno una struttura ricca.

Gli alberi forniscono una gamma di applicazioni utili da semplici come un albero genealogico a complesse come alberi nelle strutture dati dell'informatica.

Albero

UN connected acyclic graphsi chiama albero. In altre parole, un grafo connesso senza cicli è chiamato albero.

I bordi di un albero sono noti come branches. Gli elementi degli alberi sono chiamati i loro nodi. Vengono chiamati i nodi senza nodi figlioleaf nodes.

Un albero con vertici "n" ha bordi "n-1". Se ha un bordo in più rispetto a 'n-1', allora il bordo extra dovrebbe ovviamente accoppiarsi con due vertici che portano a formare un ciclo. Quindi, diventa un grafico ciclico che è una violazione per il grafico ad albero.

Example 1

Il grafico mostrato qui è un albero perché non ha cicli ed è connesso. Ha quattro vertici e tre bordi, cioè per 'n' vertici bordi 'n-1' come menzionato nella definizione.

Note - Ogni albero ha almeno due vertici di primo grado.

Example 2

Nell'esempio sopra, i vertici "a" e "d" hanno il grado uno. E gli altri due vertici "b" e "c" hanno il grado due. Ciò è possibile perché per non formare un ciclo, dovrebbero esserci almeno due bordi singoli ovunque nel grafico. Non è altro che due bordi con un grado di uno.

foresta

UN disconnected acyclic graphsi chiama foresta. In altre parole, una raccolta disgiunta di alberi è chiamata foresta.

Example

Il grafico seguente assomiglia a due sottografi; ma è un unico grafo disconnesso. Non ci sono cicli in questo grafico. Quindi, chiaramente è una foresta.

Spanning Trees

Sia G un grafo connesso, allora il sottografo H di G è chiamato spanning tree di G se -

  • H è un albero
  • H contiene tutti i vertici di G.

Uno spanning tree T di un grafo non orientato G è un sottografo che include tutti i vertici di G.

Example

Nell'esempio sopra, G è un grafo connesso e H è un sottografo di G.

Chiaramente, il grafo H non ha cicli, è un albero con sei spigoli che è uno in meno del numero totale di vertici. Quindi H è lo Spanning tree di G.

Classifica del circuito

Sia 'G' un grafo connesso con 'n' vertici e bordi 'm'. Uno spanning tree 'T' di G contiene (n-1) archi.

Pertanto, il numero di archi che è necessario eliminare da "G" per ottenere uno spanning tree = m- (n-1), che è chiamato rango del circuito di G.

Questa formula è vera, perché in uno spanning tree è necessario avere bordi "n-1". Fuori dagli archi 'm', è necessario mantenere gli archi 'n – 1' nel grafico.

Quindi, cancellando 'n – 1' archi da 'm' si ottengono gli archi da rimuovere dal grafico per ottenere uno spanning tree, che non dovrebbe formare un ciclo.

Example

Dai un'occhiata al grafico seguente:

Per il grafico dato nell'esempio sopra, hai m = 7 spigoli en = 5 vertici.

Quindi la classifica del circuito è -

G = m - (n - 1)

= 7 - (5 - 1)

= 3

Example

Sia 'G' un grafo connesso con sei vertici e il grado di ogni vertice è tre. Trova il rango del circuito "G".

Per la somma del teorema del grado dei vertici,

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

6 × 3 = 2 | E |

| E | = 9

Rango del circuito = | E | - (| V | - 1)

= 9 - (6 - 1) = 4

Teorema di Kirchoff

Il teorema di Kirchoff è utile per trovare il numero di spanning tree che possono essere formati da un grafo connesso.

Example

La matrice "A" deve essere riempita come se ci fosse un bordo tra due vertici, allora dovrebbe essere data come "1", altrimenti "0".

$$A=\begin{vmatrix}0 & a & b & c & d\\a & 0 & 1 & 1 & 1 \\b & 1 & 0 & 0 & 1\\c & 1 & 0 & 0 & 1\\d & 1 & 1 & 1 & 0 \end{vmatrix} = \begin{vmatrix} 0 & 1 & 1 & 1\\1 & 0 & 0 & 1\\1 & 0 & 0 & 1\\1 & 1 & 1 & 0\end{vmatrix}$$

Usando il teorema di Kirchoff, dovrebbe essere modificato sostituendo i valori diagonali principali con il grado dei vertici e tutti gli altri elementi con -1.A

$$=\begin{vmatrix} 3 & -1 & -1 & -1\\-1 & 2 & 0 & -1\\-1 & 0 & 2 & -1\\-1 & -1 & -1 & 3 \end{vmatrix}=M$$ $$M=\begin{vmatrix}3 & -1 & -1 & -1\\-1 & 2 & 0 & -1\\-1 & 0 & 2 & -1\\-1 & -1 & -1 & 3 \end{vmatrix} =8$$ $$Co\:\:factor\:\:of\:\:m1\:\:= \begin{vmatrix} 2 & 0 & -1\\0 & 2 & -1\\-1 & -1 & 3\end{vmatrix}$$

Pertanto, il numero di spanning tree = 8.

Se è possibile attraversare un grafico da un vertice all'altro è determinato dal modo in cui un grafico è connesso. La connettività è un concetto di base nella teoria dei grafi. La connettività definisce se un grafico è connesso o disconnesso. Ha argomenti secondari basati su bordo e vertice, noti come connettività edge e connettività vertice. Cerchiamo di discuterli in dettaglio.

Connettività

Si dice che sia un grafico connected if there is a path between every pair of vertex. Da ogni vertice a qualsiasi altro vertice, dovrebbe esserci un percorso da attraversare. Questa è chiamata connettività di un grafico. Si dice che un grafo con più vertici e bordi scollegati sia disconnesso.

Example 1

Nel grafico seguente, è possibile viaggiare da un vertice a qualsiasi altro vertice. Ad esempio, si può passare dal vertice "a" al vertice "e" utilizzando il percorso "ab-e".

Example 2

Nell'esempio seguente, l'attraversamento dal vertice "a" al vertice "f" non è possibile perché non esiste alcun percorso tra di loro direttamente o indirettamente. Quindi è un grafico disconnesso.

Cut Vertex

Sia "G" un grafo connesso. Un vertice V ∈ G è chiamato vertice tagliato di 'G', se 'G-V' (Elimina 'V' da 'G') risulta in un grafo disconnesso. La rimozione di un vertice tagliato da un grafico lo suddivide in due o più grafici.

Note - La rimozione di un vertice tagliato può rendere un grafico scollegato.

Un grafo connesso 'G' può avere al massimo (n – 2) vertici tagliati.

Example

Nel grafico seguente, i vertici "e" e "c" sono i vertici tagliati.

Rimuovendo "e" o "c", il grafico diventerà un grafico disconnesso.

Senza 'g', non c'è percorso tra il vertice 'c' e il vertice 'h' e molti altri. Quindi è un grafo disconnesso con vertice tagliato come "e". Allo stesso modo, 'c' è anche un vertice tagliato per il grafico sopra.

Bordo tagliato (ponte)

Sia "G" un grafo connesso. Un arco 'e' ∈ G è detto bordo tagliato se 'G-e' risulta in un grafo disconnesso.

Se rimuovendo un bordo in un grafico si ottengono due o più grafici, quel bordo viene chiamato bordo tagliato.

Example

Nel grafico seguente, il bordo tagliato è [(c, e)].

Rimuovendo il bordo (c, e) dal grafico, diventa un grafico disconnesso.

Nel grafico sopra, la rimozione del bordo (c, e) spezza il grafico in due che non è altro che un grafico disconnesso. Quindi, il bordo (c, e) è un bordo tagliato del grafico.

Note - Sia 'G' un grafo connesso con 'n' vertici, quindi

  • un bordo tagliato e ∈ G se e solo se il bordo 'e' non fa parte di alcun ciclo in G.

  • il numero massimo di bordi tagliati possibile è 'n-1'.

  • ogniqualvolta esistono bordi tagliati, esistono anche vertici tagliati perché almeno un vertice di un bordo tagliato è un vertice tagliato.

  • se esiste un vertice tagliato, allora un bordo tagliato può o non può esistere.

Taglia insieme di un grafico

Sia 'G' = (V, E) un grafo connesso. Un sottoinsieme E 'di E è chiamato un insieme tagliato di G se la cancellazione di tutti gli archi di E' da G fa disconnettere G.

Se l'eliminazione di un certo numero di bordi da un grafico ne causa la disconnessione, tali bordi eliminati vengono chiamati il ​​gruppo di tagli del grafico.

Example

Dai un'occhiata al grafico seguente. Il suo set di taglio è E1 = {e1, e3, e5, e8}.

Dopo aver rimosso il set di taglio E1 dal grafico, apparirà come segue:

Allo stesso modo, ci sono altri gruppi di taglio che possono disconnettere il grafico -

  • E3 = {e9} - Il più piccolo insieme di sezioni del grafico.

  • E4 = {e3, e4, e5}

Connettività Edge

Sia "G" un grafo connesso. Il numero minimo di bordi la cui rimozione rende 'G' scollegato è chiamato connettività degli spigoli di G.

Notation - λ (G)

In altre parole, il file number of edges in a smallest cut set of G è chiamata la connettività edge di G.

Se 'G' ha un bordo tagliato, allora λ (G) è 1. (connettività del bordo di G.)

Example

Dai un'occhiata al grafico seguente. Rimuovendo due bordi minimi, il grafico connesso viene disconnesso. Quindi, la sua connettività di bordo (λ (G)) è 2.

Ecco i quattro modi per scollegare il grafico rimuovendo due bordi:

Vertex Connectivity

Sia "G" un grafo connesso. Il numero minimo di vertici la cui rimozione rende "G" scollegato o riduce "G" a un grafo banale è chiamato la sua connettività di vertice.

Notation - K (G)

Example

Nel grafico sopra, la rimozione dei vertici "e" e "i" rende il grafico scollegato.

Se G ha un vertice tagliato, allora K (G) = 1.

Notation - Per qualsiasi grafo G connesso,

K (G) ≤ λ (G) ≤ δ (G)

Connettività al vertice (K (G)), connettività ai bordi (λ (G)), numero minimo di gradi di G (δ (G)).

Example

Calcola λ (G) e K (G) per il grafico seguente:

Solution

Dal grafico,

δ (Sol) = 3

K (G) ≤ λ (G) ≤ δ (G) = 3 (1)

K (G) ≥ 2 (2)

Eliminando i bordi {d, e} e {b, h}, possiamo scollegare G.

Perciò,

λ (G) = 2

2 ≤ λ (G) ≤ δ (G) = 2 (3)

Da (2) e (3), la connettività dei vertici K (G) = 2

Un grafo coprente è un sottografo che contiene tutti i vertici o tutti i bordi corrispondenti a qualche altro grafo. Un sottografo che contiene tutti i vertici è chiamato aline/edge covering. Un sottografo che contiene tutti i bordi è chiamato avertex covering.

Linea di copertura

Sia G = (V, E) un grafico. Un sottoinsieme C (E) è chiamato copertura di linea di G se ogni vertice di G è incidente con almeno un arco in C, cioè,

gradi (V) ≥ 1 ∀ V ∈ G

perché ogni vertice è connesso con un altro vertice da un bordo. Quindi ha un grado minimo di 1.

Example

Dai un'occhiata al grafico seguente:

I suoi sottografi con copertura della linea sono i seguenti:

C 1 = {{a, b}, {c, d}}

C 2 = {{a, d}, {b, c}}

C 3 = {{a, b}, {b, c}, {b, d}}

C 4 = {{a, b}, {b, c}, {c, d}}

La copertura di linea di 'G' non esiste se e solo se 'G' ha un vertice isolato. La copertura di linea di un grafo con 'n' vertici ha almeno [n / 2] bordi.

Copertura minimale

Si dice che una linea che copre C di un grafo G sia minima if no edge can be deleted from C.

Example

Nel grafico sopra, i sottografi che coprono la linea sono i seguenti:

C 1 = {{a, b}, {c, d}}

C 2 = {{a, d}, {b, c}}

C 3 = {{a, b}, {b, c}, {b, d}}

C 4 = {{a, b}, {b, c}, {c, d}}

Qui, C 1 , C 2 , C 3 sono coperture di linea minime, mentre C 4 non lo è perché possiamo eliminare {b, c}.

Minimum Line Covering

It is also known as Smallest Minimal Line Covering. A minimal line covering with minimum number of edges is called a minimum line covering of ‘G’. The number of edges in a minimum line covering in ‘G’ is called the line covering number of ‘G’ (α1).

Example

In the above example, C1 and C2 are the minimum line covering of G and α1 = 2.

  • Every line covering contains a minimal line covering.

  • Every line covering does not contain a minimum line covering (C3 does not contain any minimum line covering.

  • No minimal line covering contains a cycle.

  • If a line covering ‘C’ contains no paths of length 3 or more, then ‘C’ is a minimal line covering because all the components of ‘C’ are star graph and from a star graph, no edge can be deleted.

Vertex Covering

Let ‘G’ = (V, E) be a graph. A subset K of V is called a vertex covering of ‘G’, if every edge of ‘G’ is incident with or covered by a vertex in ‘K’.

Example

Take a look at the following graph −

The subgraphs that can be derived from the above graph are as follows −

K1 = {b, c}

K2 = {a, b, c}

K3 = {b, c, d}

K4 = {a, d}

Here, K1, K2, and K3 have vertex covering, whereas K4 does not have any vertex covering as it does not cover the edge {bc}.

Minimal Vertex Covering

A vertex ‘K’ of graph ‘G’ is said to be minimal vertex covering if no vertex can be deleted from ‘K’.

Example

In the above graph, the subgraphs having vertex covering are as follows −

K1 = {b, c}

K2 = {a, b, c}

K3 = {b, c, d}

Here, K1 and K2 are minimal vertex coverings, whereas in K3, vertex ‘d’ can be deleted.

Minimum Vertex Covering

It is also known as the smallest minimal vertex covering. A minimal vertex covering of graph ‘G’ with minimum number of vertices is called the minimum vertex covering.

The number of vertices in a minimum vertex covering of ‘G’ is called the vertex covering number of G (α2).

Example

In the following graph, the subgraphs having vertex covering are as follows −

K1 = {b, c}

K2 = {a, b, c}

K3 = {b, c, d}

Here, K1 is a minimum vertex cover of G, as it has only two vertices. α2 = 2.

A matching graph is a subgraph of a graph where there are no edges adjacent to each other. Simply, there should not be any common vertex between any two edges.

Matching

Let ‘G’ = (V, E) be a graph. A subgraph is called a matching M(G), if each vertex of G is incident with at most one edge in M, i.e.,

deg(V) ≤ 1 ∀ V ∈ G

which means in the matching graph M(G), the vertices should have a degree of 1 or 0, where the edges should be incident from the graph G.

Notation − M(G)

Example

In a matching,

if deg(V) = 1, then (V) is said to be matched

if deg(V) = 0, then (V) is not matched.

In a matching, no two edges are adjacent. It is because if any two edges are adjacent, then the degree of the vertex which is joining those two edges will have a degree of 2 which violates the matching rule.

Maximal Matching

A matching M of graph ‘G’ is said to maximal if no other edges of ‘G’ can be added to M.

Example

M1, M2, M3 from the above graph are the maximal matching of G.

Maximum Matching

It is also known as largest maximal matching. Maximum matching is defined as the maximal matching with maximum number of edges.

The number of edges in the maximum matching of ‘G’ is called its matching number.

Example

For a graph given in the above example, M1 and M2 are the maximum matching of ‘G’ and its matching number is 2. Hence by using the graph G, we can form only the subgraphs with only 2 edges maximum. Hence we have the matching number as two.

Perfect Matching

A matching (M) of graph (G) is said to be a perfect match, if every vertex of graph g (G) is incident to exactly one edge of the matching (M), i.e.,

deg(V) = 1 ∀ V

The degree of each and every vertex in the subgraph should have a degree of 1.

Example

In the following graphs, M1 and M2 are examples of perfect matching of G.

Note − Every perfect matching of graph is also a maximum matching of graph, because there is no chance of adding one more edge in a perfect matching graph.

A maximum matching of graph need not be perfect. If a graph ‘G’ has a perfect match, then the number of vertices |V(G)| is even. If it is odd, then the last vertex pairs with the other vertex, and finally there remains a single vertex which cannot be paired with any other vertex for which the degree is zero. It clearly violates the perfect matching principle.

Example

Note − The converse of the above statement need not be true. If G has even number of vertices, then M1 need not be perfect.

Example

It is matching, but it is not a perfect match, even though it has even number of vertices.

Independent sets are represented in sets, in which

  • there should not be any edges adjacent to each other. There should not be any common vertex between any two edges.

  • there should not be any vertices adjacent to each other. There should not be any common edge between any two vertices.

Independent Line Set

Let ‘G’ = (V, E) be a graph. A subset L of E is called an independent line set of ‘G’ if no two edges in L are adjacent. Such a set is called an independent line set.

Example

Let us consider the following subsets −

L1 = {a,b}
L2 = {a,b} {c,e}
L3 = {a,d} {b,c}

In this example, the subsets L2 and L3 are clearly not the adjacent edges in the given graph. They are independent line sets. However L1 is not an independent line set, as for making an independent line set, there should be at least two edges.

Maximal Independent Line Set

An independent line set is said to be the maximal independent line set of a graph ‘G’ if no other edge of ‘G’ can be added to ‘L’.

Example

Let us consider the following subsets −

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L2 and L3 are maximal independent line sets/maximal matching. As for only these two subsets, there is no chance of adding any other edge which is not an adjacent. Hence these two subsets are considered as the maximal independent line sets.

Maximum Independent Line Set

A maximum independent line set of ‘G’ with maximum number of edges is called a maximum independent line set of ‘G’.

Number of edges in a maximum independent line set of G (β1)
   = Line independent number of G
   = Matching number of G

Example

Let us consider the following subsets −

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L3 is the maximum independent line set of G with maximum edges which are not the adjacent edges in graph and is denoted by β1 = 3.

Note − For any graph G with no isolated vertex,

α1 + β1 = number of vertices in a graph = |V|

Example

Line covering number of Kn/Cn/wn,

$$\alpha 1 = \lceil\frac{n}{2}\rceil\begin{cases}\frac{n}{2}\:if\:n\:is\:even \\\frac{n+1}{2}\:if\:n\:is\:odd\end{cases}$$

Line independent number (Matching number) = β1 = [n/2] α1 + β1 = n.

Independent Vertex Set

Let ‘G’ = (V, E) be a graph. A subset of ‘V’ is called an independent set of ‘G’ if no two vertices in ‘S’ are adjacent.

Example

Consider the following subsets from the above graphs −

S1 = {e}

S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

Clearly S1 is not an independent vertex set, because for getting an independent vertex set, there should be at least two vertices in the from a graph. But here it is not that case. The subsets S2, S3, and S4 are the independent vertex sets because there is no vertex that is adjacent to any one vertex from the subsets.

Maximal Independent Vertex Set

Sia 'G' un grafo, allora un insieme di vertici indipendente di 'G' si dice che sia massimo se nessun altro vertice di 'G' può essere aggiunto a 'S'.

Example

Considera i seguenti sottoinsiemi dai grafici sopra.

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

S 2 e S 3 sono i massimi insiemi di vertici indipendenti di "G". In S 1 e S 4 , possiamo aggiungere altri vertici; ma in S 2 e S 3 , non possiamo aggiungere nessun altro vertice.

Set massimo di vertici indipendenti

Un massimo insieme di vertici indipendenti di 'G' con il numero massimo di vertici è chiamato come il massimo insieme di vertici indipendenti.

Example

Considera i seguenti sottoinsiemi dal grafico sopra:

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

Solo S 3 è il massimo insieme di vertici indipendenti, poiché copre il numero più alto di vertici. Il numero di vertici in un massimo insieme di vertici indipendenti di 'G' è chiamato numero di vertici indipendenti di G (β 2 ).

Example

Per il grafico completo K n ,

Numero di copertura del vertice = α 2 = n − 1

Numero indipendente dal vertice = β 2 = 1

Hai α 2 + β 2 = n

In un grafo completo, ogni vertice è adiacente ai suoi rimanenti (n - 1) vertici. Pertanto, un insieme massimo indipendente di K n contiene solo un vertice.

Pertanto, β 2 = 1

e α 2 = | v | - β 2 = n-1

Note - Per qualsiasi grafico 'G' = (V, E)

  • α 2 + β 2 = | v |
  • Se 'S' è un insieme di vertici indipendente di 'G', allora (V - S) è una copertura di vertici di G.

La colorazione del grafico non è altro che un modo semplice per etichettare i componenti del grafico come vertici, bordi e regioni sotto alcuni vincoli. In un grafico, non ci sono due vertici adiacenti, bordi adiacenti o regioni adiacenti colorati con un numero minimo di colori. Questo numero è chiamatochromatic number e il grafico si chiama a properly colored graph.

Durante la colorazione del grafico, i vincoli impostati sul grafico sono i colori, l'ordine di colorazione, il modo di assegnare il colore, ecc. Viene data una colorazione a un vertice oa una particolare regione. Pertanto, i vertici o le regioni aventi gli stessi colori formano insiemi indipendenti.

Colorazione dei vertici

La colorazione dei vertici è un'assegnazione di colori ai vertici di un grafo 'G' in modo tale che non ci siano due vertici adiacenti dello stesso colore. In poche parole, non esistono due vertici di un bordo dello stesso colore.

Numero cromatico

Il numero minimo di colori richiesto per la colorazione dei vertici del grafo "G" è chiamato come numero cromatico di G, indicato con X (G).

χ (G) = 1 se e solo se 'G' è un grafo nullo. Se 'G' non è un grafo nullo, allora χ (G) ≥ 2.

Example

Note - Un grafo 'G' si dice copribile con n se c'è una colorazione dei vertici che usa al massimo n colori, cioè X (G) ≤ n.

Colorazione della regione

La colorazione della regione è un'assegnazione di colori alle regioni di un grafico planare in modo tale che non ci siano due regioni adiacenti dello stesso colore. Si dice che due regioni siano adiacenti se hanno un bordo comune.

Example

Dai un'occhiata al grafico seguente. Le regioni "aeb" e "befc" sono adiacenti, poiché esiste un confine comune "be" tra queste due regioni.

Allo stesso modo, anche le altre regioni sono colorate in base all'adiacenza. Questo grafico è colorato come segue:

Example

Il numero cromatico di Kn è

  • n
  • n–1
  • [n/2]
  • [n/2]

Considera questo esempio con K 4 .

Nel grafo completo, ogni vertice è adiacente ai rimanenti (n - 1) vertici. Quindi, ogni vertice richiede un nuovo colore. Da qui il numero cromatico di K n = n.

Applicazioni della colorazione dei grafici

La colorazione dei grafi è uno dei concetti più importanti nella teoria dei grafi. Viene utilizzato in molte applicazioni in tempo reale dell'informatica come:

  • Clustering
  • Estrazione dei dati
  • Acquisizione di immagini
  • Segmentazione delle immagini
  • Networking
  • Assegnazione delle risorse
  • Pianificazione dei processi

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 |

Un grafo è attraversabile se è possibile disegnare un percorso tra tutti i vertici senza ripercorrere lo stesso percorso. Sulla base di questo percorso, ci sono alcune categorie come il percorso di Eulero e il circuito di Eulero che sono descritti in questo capitolo.

Sentiero di Eulero

Il percorso di Eulero contiene ogni lato di "G" esattamente una volta e ogni vertice di "G" almeno una volta. Si dice che un grafo connesso G sia attraversabile se contiene un percorso di Eulero.

Example

Sentiero di Eulero = dcabde.

Circuito di Eulero

Nel cammino di Eulero, se il vertice iniziale è uguale al vertice finale, allora è chiamato circuito di Eulero.

Example

Euler’s Path = abcdagfeca.

Teorema del circuito di Eulero

Un grafo connesso 'G' è attraversabile se e solo se il numero di vertici con grado dispari in G è esattamente 2 o 0. Un grafo connesso G può contenere un percorso di Eulero, ma non un circuito di Eulero, se ha esattamente due vertici con un grado strano.

Note - Questo percorso di Eulero inizia con un vertice di grado dispari e termina con l'altro vertice di grado dispari.

Example

Euler’s Path- beabdca non è un circuito di Eulero, ma è un percorso di Eulero. Chiaramente ha esattamente 2 vertici di grado dispari.

Note - In un grafo connesso G, se il numero di vertici con grado dispari = 0, allora esiste il circuito di Eulero.

Grafico hamiltoniano

Si dice che un grafo connesso G sia un grafo hamiltoniano, se esiste un ciclo che contiene tutti i vertici di G.

Ogni ciclo è un circuito ma un circuito può contenere più cicli. Un tale ciclo è chiamato aHamiltonian cycle di G.

Sentiero Hamiltoniano

Un grafo connesso si dice hamiltoniano se contiene ogni vertice di G esattamente una volta. Tale percorso è chiamato aHamiltonian path.

Example

Hamiltonian Path- edbac.

Note

  • Il circuito di Eulero contiene ciascun bordo del grafico esattamente una volta.

  • In un ciclo hamiltoniano, alcuni bordi del grafico possono essere saltati.

Example

Dai un'occhiata al grafico seguente:

Per il grafico mostrato sopra -

  • Il sentiero di Eulero esiste - falso

  • Il circuito di Eulero esiste - falso

  • Il ciclo hamiltoniano esiste - vero

  • Il percorso hamiltoniano esiste - vero

G ha quattro vertici con grado dispari, quindi non è attraversabile. Saltando gli archi interni, il grafo ha un ciclo hamiltoniano passante per tutti i vertici.

In questo capitolo tratteremo alcuni esempi standard per dimostrare i concetti che abbiamo già discusso nei capitoli precedenti.

Esempio 1

Find the number of spanning trees in the following graph.

Soluzione

Il numero di spanning tree ottenuto dal grafico sopra è 3. Sono i seguenti:

Questi tre sono gli spanning tree per i grafici dati. Qui i grafici I e II sono isomorfi tra loro. Chiaramente, il numero di spanning tree non isomorfi è due.

Esempio 2

How many simple non-isomorphic graphs are possible with 3 vertices?

Soluzione

Sono possibili 4 grafici non isomorfi con 3 vertici. Sono mostrati di seguito.

Esempio 3

Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.

Soluzione

Dalla somma dei gradi teorema,

20 Σ i = 1 deg (Vi) = 2 | E |

20 (3) = 2 | E |

| E | = 30

Secondo la formula di Eulero,

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

20+ | R | = 30 + 2

| R | = 12

Quindi, il numero di regioni è 12.

Esempio 4

What is the chromatic number of complete graph Kn?

Soluzione

In un grafo completo, ogni vertice è adiacente ai rimanenti (n – 1) vertici. Quindi, ogni vertice richiede un nuovo colore. Da qui il numero cromatico K n = n.

Esempio 5

What is the matching number for the following graph?

Soluzione

Numero di vertici = 9

Possiamo abbinare solo 8 vertici.

Il numero corrispondente è 4.

Esempio 6

What is the line covering number of for the following graph?

Soluzione

Numero di vertici = | V | = n = 7

Numero di copertura della linea = (α 1 ) ≥ [n / 2] = 3

α 1 ≥ 3

Usando 3 bordi, possiamo coprire tutti i vertici.

Quindi, il numero di copertura della linea è 3.