Teoría de grafos - Propiedades básicas
Los gráficos tienen varias propiedades que se utilizan para la caracterización de los gráficos en función de sus estructuras. Estas propiedades se definen en términos específicos pertenecientes al dominio de la teoría de grafos. En este capítulo, discutiremos algunas propiedades básicas que son comunes en todas las gráficas.
Distancia entre dos vértices
Es el número de aristas en una ruta más corta entre el vértice U y el vértice V. Si hay varias rutas que conectan dos vértices, entonces la ruta más corta se considera como la distancia entre los dos vértices.
Notación - d (U, V)
Puede haber cualquier número de caminos presentes de un vértice a otro. Entre ellos, debe elegir solo el más corto.
Example
Eche un vistazo al siguiente gráfico:
Aquí, la distancia desde el vértice 'd' al vértice 'e' o simplemente 'de' es 1 ya que hay un borde entre ellos. Hay muchos caminos desde el vértice 'd' al vértice 'e' -
- da, ab, be
- df, fg, ge
- de (Se considera para la distancia entre los vértices)
- df, fc, ca, ab, be
- da, ac, cf, fg, ge
Excentricidad de un vértice
La distancia máxima entre un vértice y todos los demás vértices se considera la excentricidad del vértice.
Notación - e (V)
Se toma la distancia desde un vértice particular a todos los demás vértices del gráfico y, entre esas distancias, la excentricidad es la más alta de las distancias.
Example
En el gráfico anterior, la excentricidad de 'a' es 3.
La distancia de 'a' a 'b' es 1 ('ab'),
de 'a' a 'c' es 1 ('ac'),
de 'a' a 'd' es 1 ('ad'),
de 'a' a 'e' es 2 ('ab' - 'be') o ('ad' - 'de'),
de 'a' a 'f' es 2 ('ac' - 'cf') o ('ad' - 'df'),
de 'a' a 'g' es 3 ('ac' - 'cf' - 'fg') o ('ad' - 'df' - 'fg').
Entonces la excentricidad es 3, que es un máximo desde el vértice 'a' de la distancia entre 'ag' que es máxima.
En otras palabras,
e (b) = 3
e (c) = 3
e (d) = 2
e (e) = 3
e (f) = 3
e (g) = 3
Radio de un gráfico conectado
La excentricidad mínima de todos los vértices se considera como el radio del Gráfico G. El mínimo entre todas las distancias máximas entre un vértice y todos los demás vértices se considera como el radio del Gráfico G.
Notación - r (G)
De todas las excentricidades de los vértices en un gráfico, el radio del gráfico conectado es el mínimo de todas esas excentricidades.
Example
En el gráfico anterior r (G) = 2, que es la excentricidad mínima para 'd'.
Diámetro de un gráfico
La excentricidad máxima de todos los vértices se considera como el diámetro del Gráfico G. El máximo entre todas las distancias entre un vértice y todos los demás vértices se considera como el diámetro del Gráfico G.
Notation − d(G) - De todas las excentricidades de los vértices en un gráfico, el diámetro del gráfico conectado es el máximo de todas esas excentricidades.
Example
En el gráfico anterior, d (G) = 3; que es la máxima excentricidad.
Punto central
Si la excentricidad de un gráfico es igual a su radio, entonces se conoce como el punto central del gráfico. Si
e (V) = r (V),
entonces 'V' es el punto central del Gráfico 'G'.
Example
En el gráfico de ejemplo, 'd' es el punto central del gráfico.
e (d) = r (d) = 2
Centrar
El conjunto de todos los puntos centrales de 'G' se denomina centro del gráfico.
Example
En el gráfico de ejemplo, {'d'} es el centro del gráfico.
Circunferencia
los number of edges in the longest cycle of ‘G’ se llama como la circunferencia de 'G'.
Example
En el gráfico de ejemplo, la circunferencia es 6, que derivamos del ciclo más largo acfgeba o acfdeba.
Circunferencia
El número de aristas en el ciclo más corto de 'G' se llama Circunferencia.
Notation: g (G).
Example - En el gráfico de ejemplo, la circunferencia del gráfico es 4, que derivamos del ciclo más corto acfda o dfged o abeda.
Teorema de la suma de grados de vértices
Si G = (V, E) es un gráfico no dirigido con vértices V = {V 1 , V 2 ,… V n } entonces
Corollary 1
Si G = (V, E) es un gráfico dirigido con vértices V = {V 1 , V 2 ,… V n }, entonces
Corollary 2
En cualquier gráfico no dirigido, el número de vértices con grado impar es par.
Corollary 3
En una gráfica no dirigida, si el grado de cada vértice es k, entonces
Corollary 4
En una gráfica no dirigida, si el grado de cada vértice es al menos k, entonces
| Corollary 5
En una gráfica no dirigida, si el grado de cada vértice es como máximo k, entonces