Teoria dei grafi - Fondamenti

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