Teoria dei grafi - Proprietà di base
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
Corollary 1
Se G = (V, E) è un grafo orientato con vertici V = {V 1 , V 2 ,… V n }, allora
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
Corollary 4
In un grafo non orientato, se il grado di ogni vertice è almeno k, allora
| Corollary 5
In un grafo non diretto, se il grado di ogni vertice è al massimo k, allora