Matemáticas | Conceptos básicos de la teoría de grafos – Conjunto 2

Prerrequisito: fundamentos de la teoría de grafos: conjunto 1
Un gráfico es una estructura que equivale a un conjunto de objetos en los que algunos pares de objetos están en algún sentido «relacionados». Los objetos del grafo corresponden a vértices y las relaciones entre ellos corresponden a aristas . Un gráfico se representa esquemáticamente como un conjunto de puntos que representan vértices conectados por líneas o curvas que representan bordes.
Formalmente,

“Un grafo $G = (V, E)$ consta de $V$ , un conjunto no vacío de vértices (o Nodes) y $mi$ , un conjunto de aristas . Cada borde tiene uno o dos vértices asociados, llamados puntos finales .

Tipos de gráficos: Hay varios tipos de gráficos que se distinguen en función de los bordes, su dirección, su peso, etc.

1. Gráfico simple: un gráfico en el que cada borde conecta dos vértices diferentes y donde dos bordes no conectan el mismo par de vértices se llama gráfico simple. Por ejemplo, considere el siguiente gráfico:

El gráfico anterior es un gráfico simple, ya que ningún vértice tiene un bucle propio y no hay dos vértices que tengan más de una arista que los conecte.
Los bordes se denotan por los vértices que conectan: $\{A,B\}$ es el borde que conecta los vértices $A$ y $B$ .

2. Multigrafo: un grafo en el que varias aristas pueden conectar el mismo par de vértices se denomina multigrafo.
Dado que puede haber múltiples aristas entre el mismo par de vértices, la multiplicidad de aristas indica el número de aristas entre dos vértices.

El gráfico anterior es un multigrafo ya que hay varios bordes entre $B$ y $C$ . La multiplicidad de las aristas $\{ANTES DE CRISTO\}$ es 2.

En algunos gráficos, a diferencia del que se muestra arriba, los bordes están dirigidos . Esto significa que la relación entre los objetos es unidireccional y no bidireccional. La dirección de los bordes puede ser importante en algunas aplicaciones.

Según si las aristas son dirigidas o no, podemos tener gráficos dirigidos y gráficos no dirigidos . Esta propiedad se puede extender a grafos y multigrafos simples para obtener grafos simples dirigidos o no dirigidos y multigrafos dirigidos o no dirigidos.

Terminología gráfica básica:

En la discusión anterior, ya se han explicado algunos términos relacionados con los gráficos, como vértices, aristas, aristas dirigidas y no dirigidas, etc. Hay más términos que describen las propiedades de los vértices y las aristas.

Adyacencia: en un gráfico, $GRAMO$ dos vértices $tu$ y $v$ se dice que son adyacentes si son los extremos de una arista. Se dice que la arista $\{u, v\} - mi$ es incidente con los vértices.
En caso de que el borde esté dirigido, $tu$ se dice que es adyacente $v$ y $v$ se dice que es adyacente desde $tu$ . Aquí, $tu$ se dice que es el vértice inicial y $v$ se dice que es el vértice terminal .
Grado: el grado de un vértice es el número de aristas que inciden con él, excepto el bucle propio que contribuye dos veces al grado del vértice. El grado de un vértice $tu$ se denota como $grado(u)$ .
En el caso de gráficos dirigidos, el grado se clasifica además como de grado de entrada y de grado de salida . El grado de entrada de un vértice es el número de aristas con el vértice dado como vértice terminal. El grado de salida de un vértice es el número de aristas con el vértice dado como vértice inicial. El grado de entrada se denota como $grado^-(u)$ y el grado de salida se denota como $grados^+(u)$ .
Por ejemplo, en el gráfico dirigido que se muestra arriba que representa vuelos entre ciudades, el grado de entrada del vértice “Delhi” es 3 y su grado de salida también es 3.

Nota: Si un vértice tiene grado cero, se llama aislado . Si el grado es uno, entonces se llama colgante .

Teorema del apretón de manos:

¿Qué se obtendría si se suman los grados de todos los vértices de un gráfico? En el caso de un grafo no dirigido, cada arista contribuye dos veces, una por su vértice inicial y la segunda por su vértice terminal. Entonces la suma de los grados es igual al doble del número de aristas. Este hecho se establece en el teorema del apretón de manos.

Let  be an undirected graph with  edges. Then





In case G is a directed graph,

El teorema del apretón de manos, para grafos no dirigidos, tiene un resultado interesante:

An undirected graph has an even number of vertices of odd degree.

Demostración: Sean $V_{1}$ y $V_{2}$ sean los conjuntos de vértices de grados pares e impares respectivamente.
Sabemos por el teorema del apretón de manos que,
$2e = \sum_{u\in V} deg(u)$
Entonces,
$2e = \sum_{u\in V} deg(u) = \sum_{u\in V_{1}} deg(u) + \sum_{u\in V_{2}} deg(u)$
La suma de grados de vértices con grados pares es par. El LHS también es par, lo que significa que la suma de los grados de los vértices con grados impares debe ser par.
Por tanto, el número de vértices de grado impar es par.

Algunos gráficos simples especiales:

1. Gráficos completos: un gráfico simple de $n$ vértices que tiene exactamente una arista entre cada par de vértices se denomina gráfico completo. Una gráfica completa de $n$ vértices se denota por $K_{n}$ . El número total de aristas es n*(n-1)/2 con n vértices en el gráfico completo.

Complete Graphs, K2, K3.. to K7

2. Ciclos: los ciclos son gráficos simples con vértices $n \geq 3$ y aristas $\{1, 2\},\: \{2, 3\}...\: \{n-1, n\}\: and\: \{n, 1\}$ . El ciclo con $n$ vértices se denota como $C_{n}$ . El número total de aristas es n con n vértices en el gráfico de ciclo.

3. Ruedas: una rueda es como un ciclo, con un vértice adicional que está conectado a todos los demás vértices. Las ruedas de $n$ vértices con 1 vértice adicional se denotan por $W_{n}$ . El número total de aristas es 2*(n-1) con n vértices en el gráfico de ruedas.

Wheels- W4, W5, W6 and W7

4. Hipercubo: el hipercubo o n-cubo es un gráfico con $2^n$ vértices, cada uno representado por una string de n bits. Los vértices que difieren como máximo en 1 bit están conectados por aristas. Un hipercubo de $2^n$ vértices se denota por $Q_{n}$ . El número total de aristas es n* $2^{n-1}$ con $2^n$ vértices en el gráfico de cubo.

5. Gráficos bipartitos: se dice que un gráfico simple $G$ es bipartito si su conjunto de vértices $V$ se puede dividir en dos conjuntos disjuntos, de modo que cada borde $G$ tenga su vértice inicial en el primer conjunto y el vértice terminal en el segundo conjunto. El número total de aristas es (n*m) con (n+m) vértices en un gráfico bipartito.

Bipartite Graph example

Teorema: un gráfico simple es bipartito si y solo si es posible asignar uno de dos
colores diferentes a cada vértice del gráfico de modo que no se asigne el
mismo color a dos adyacentes.

Se dice que un grafo bipartito con vértices $m$ y $n$ en sus dos subconjuntos disjuntos está completo si hay una arista desde cada vértice del primer conjunto hasta cada vértice del segundo conjunto, para un total de aristas $mn$ . Un gráfico bipartito completo con $m$ vértices en el primer conjunto y $n$ vértices en el segundo conjunto se denota como $K_{m,n}$ .

Preguntas de GATE CS Corner

Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.

1. GATE CS 2013, Pregunta 25
2. GATE CS 2014 Conjunto-1, Pregunta 61
3. GATE CS 2006, Pregunta 71
4. GATE CS 2002, Pregunta 25
5. GATE CS 2004, Pregunta 37
6. GATE CS 2014 Conjunto- 2, pregunta 13

Referencias-

Gráficos – Wikipedia
Matemáticas discretas y sus aplicaciones, por Kenneth H Rosen

Este artículo es una contribución de Chirag Manwani . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta