Grafici e modelli grafici

La parte precedente ha portato alla luce i diversi strumenti per il ragionamento, la verifica e la risoluzione dei problemi. In questa parte, studieremo le strutture discrete che costituiscono la base per la formulazione di molti problemi della vita reale.

Le due strutture discrete che tratteremo sono i grafici e gli alberi. Un grafo è un insieme di punti, chiamati nodi o vertici, che sono interconnessi da un insieme di linee chiamate bordi. Lo studio dei grafici, ograph theory è una parte importante di una serie di discipline nei campi della matematica, dell'ingegneria e dell'informatica.

Cos'è un grafico?

Definition - Un grafo (indicato come $ G = (V, E) $) è costituito da un insieme non vuoto di vertici o nodi V e da un insieme di archi E.

Example - Consideriamo che un grafico è $ G = (V, E) $ dove $ V = \ lbrace a, b, c, d \ rbrace $ e $ E = \ lbrace \ lbrace a, b \ rbrace, \ lbrace a , c \ rbrace, \ lbrace b, c \ rbrace, \ lbrace c, d \ rbrace \ rbrace $

Degree of a Vertex - Il grado di un vertice V di un grafo G (indicato con deg (V)) è il numero di archi incidenti con il vertice V.

Vertice Grado Pari dispari
un 2 anche
b 2 anche
c 3 dispari
d 1 dispari

Even and Odd Vertex - Se il grado di un vertice è pari, il vertice è chiamato vertice pari e se il grado di un vertice è dispari, il vertice è chiamato vertice dispari.

Degree of a Graph- Il grado di un grafico è il massimo grado di vertice di quel grafico. Per il grafico sopra, il grado del grafico è 3.

The Handshaking Lemma - In un grafico, la somma di tutti i gradi di tutti i vertici è uguale al doppio del numero di bordi.

Tipi di grafici

Esistono diversi tipi di grafici, che impareremo nella sezione seguente.

Grafico nullo

Un grafo nullo non ha bordi. Il grafo nullo di $ n $ vertici è indicato da $ N_n $

Grafico semplice

Un grafo è chiamato grafo semplice / grafo rigoroso se il grafo non è orientato e non contiene loop o bordi multipli.

Multi-Graph

Se in un grafo sono consentiti più bordi tra lo stesso insieme di vertici, si parla di Multigraph. In altre parole, è un grafico con almeno un loop o più bordi.

Grafico diretto e non orientato

Un grafo $ G = (V, E) $ è chiamato grafo diretto se l'insieme di archi è costituito da una coppia di vertici ordinata e un grafo è detto non orientato se l'insieme di archi è composto da una coppia di vertici non ordinati.

Grafico connesso e disconnesso

Un grafo è connesso se due vertici del grafo sono collegati da un percorso; mentre un grafo è disconnesso se almeno due vertici del grafo non sono collegati da un percorso. Se un grafo G è disconnesso, ogni sottografo connesso massimale di $ G $ è chiamato componente connesso del grafo $ G $.

Grafico regolare

Un grafo è regolare se tutti i vertici del grafo hanno lo stesso grado. In un grafo regolare G di grado $ r $, il grado di ciascun vertice di $ G $ è r.

Grafico completo

Un grafo è chiamato grafo completo se ogni coppia di due vertici è unita da esattamente un bordo. Il grafo completo con n vertici è indicato con $ K_n $

Grafico del ciclo

Se un grafico è costituito da un singolo ciclo, si chiama grafico del ciclo. Il grafo del ciclo con n vertici è indicato con $ C_n $

Grafico bipartito

Se l'insieme dei vertici di un grafo G può essere suddiviso in due insiemi disgiunti, $ V_1 $ e $ V_2 $, in modo tale che ciascun arco nel grafico si unisca a un vertice in $ V_1 $ a un vertice in $ V_2 $ e non ci sono archi in G che collegano due vertici in $ V_1 $ o due vertici in $ V_2 $, quindi il grafo $ G $ è chiamato grafo bipartito.

Grafico bipartito completo

Un grafo bipartito completo è un grafo bipartito in cui ogni vertice nel primo insieme è unito a ogni singolo vertice nel secondo insieme. Il grafo bipartito completo è indicato con $ K_ {x, y} $ dove il grafo $ G $ contiene $ x $ vertici nel primo insieme e $ y $ vertici nel secondo insieme.

Rappresentazione di grafici

Esistono principalmente due modi per rappresentare un grafico:

  • Matrice di adiacenza
  • Elenco di adiacenza

Matrice di adiacenza

Una matrice di adiacenza $ A [V] [V] $ è un array 2D di dimensione $ V \ times V $ dove $ V $ è il numero di vertici in un grafo non orientato. Se c'è un arco compreso tra $ V_x $ e $ V_y $, il valore di $ A [V_x] [V_y] = 1 $ e $ A [V_y] [V_x] = 1 $, altrimenti il ​​valore sarà zero. E per un grafico orientato, se c'è un arco compreso tra $ V_x $ e $ V_y $, allora il valore di $ A [V_x] [V_y] = 1 $, altrimenti il ​​valore sarà zero.

Adjacency Matrix of an Undirected Graph

Consideriamo il seguente grafo non orientato e costruiamo la matrice di adiacenza -

La matrice di adiacenza del grafo non orientato sopra sarà:

a

b

c

d

a

0

1

1

0

b

1

0

1

0

c

1

1

0

1

d

0

0

1

0

Adjacency Matrix of a Directed Graph

Consideriamo il seguente grafo orientato e costruiamo la sua matrice di adiacenza:

La matrice di adiacenza del grafo diretto sopra sarà:

a

b

c

d

a

0

1

1

0

b

0

0

1

0

c

0

0

0

1

d

0

0

0

0

Elenco di adiacenza

Nella lista di adiacenza, un array $ (A [V]) $ di liste collegate viene utilizzato per rappresentare il grafo G con $ V $ numero di vertici. Una voce $ A [V_x] $ rappresenta l'elenco collegato di vertici adiacenti al $ vertice $ Vx-esimo. L'elenco di adiacenza del grafico non orientato è come mostrato nella figura seguente:

Grafico planare vs. grafico non planare

Planar graph- Un grafico $ G $ è chiamato grafico planare se può essere disegnato in un piano senza che alcun bordo sia incrociato. Se disegniamo il grafico nel piano senza attraversare i bordi, si parla di incorporamento del grafico nel piano.

Non-planar graph - Un grafico non è planare se non può essere disegnato su un piano senza che i bordi del grafico si intersechino.

Isomorfismo

Se due grafi G e H contengono lo stesso numero di vertici collegati nello stesso modo, vengono chiamati grafi isomorfi (indicati con $ G \ cong H $).

È più facile controllare il non isomorfismo che l'isomorfismo. Se si verifica una delle seguenti condizioni, due grafici non sono isomorfi:

  • Il numero di componenti collegati è diverso
  • Le cardinalità dei vertici sono diverse
  • Le cardinalità edge-set sono diverse
  • Le sequenze dei gradi sono diverse

Esempio

I grafici seguenti sono isomorfi:

Omomorfismo

Un omomorfismo da un grafico $ G $ a un grafico $ H $ è una mappatura (potrebbe non essere una mappatura biiettiva) $ h: G \ rightarrow H $ tale che - $ (x, y) \ in E (G) \ rightarrow (h (x), h (y)) \ in E (H) $. Mappa i vertici adiacenti del grafo $ G $ ai vertici adiacenti del grafo $ H $.

Proprietà degli omomorfismi

  • Un omomorfismo è un isomorfismo se è una mappatura biiettiva.

  • L'omomorfismo preserva sempre i bordi e la connessione di un grafico.

  • Anche le composizioni di omomorfismi sono omomorfismi.

  • Scoprire se esiste un grafo omomorfico di un altro grafo è un problema NPcompleto.

Grafici di Eulero

Un grafo connesso $ G $ è chiamato grafo di Eulero, se c'è una traccia chiusa che include ogni lato del grafico $ G $. Un percorso di Eulero è un percorso che utilizza ogni bordo di un grafico esattamente una volta. Un percorso di Eulero inizia e finisce in vertici diversi.

Un circuito di Eulero è un circuito che utilizza ogni bordo di un grafico esattamente una volta. Un circuito di Eulero inizia e finisce sempre allo stesso vertice. Un grafo connesso $ G $ è un grafo di Eulero se e solo se tutti i vertici di $ G $ sono di grado pari, e un grafo connesso $ G $ è euleriano se e solo se il suo insieme di archi può essere scomposto in cicli.

Il grafico sopra è un grafico di Eulero come $ "a \: 1 \: b \: 2 \: c \: 3 \: d \: 4 \: e \: 5 \: c \: 6 \: f \: 7 \: g ”$ copre tutti i bordi del grafico.

Grafici Hamiltoniani

Un grafo connesso $ G $ è chiamato grafo hamiltoniano se c'è un ciclo che include ogni vertice di $ G $ e il ciclo è chiamato ciclo hamiltoniano. La passeggiata hamiltoniana nel grafico $ G $ è una passeggiata che attraversa ciascun vertice esattamente una volta.

Se $ G $ è un grafo semplice con n vertici, dove $ n \ geq 3 $ Se $ deg (v) \ geq \ frac {n} {2} $ per ogni vertice $ v $, allora il grafico $ G $ è Grafico hamiltoniano. Questo è chiamatoDirac's Theorem.

Se $ G $ è un grafo semplice con $ n $ vertici, dove $ n \ geq 2 $ if $ deg (x) + deg (y) \ geq n $ per ogni coppia di vertici non adiacenti x e y, allora il graph $ G $ è il grafico hamiltoniano. Questo è chiamatoOre's theorem.