13.2 Grafos.

13.2.1 Definición. Un grafo G está formado por:

Un vértice que no está unido a otro vértice o a sí mismo se llama vértice aislado.

Ejemplo 1

Para el grafo siguiente:

  1. Escribir el conjunto de vértices.

  2. Escribir el conjunto de aristas.

  3. Hallar los vértices aislados.

  4. Hallar los lazos.

  5. Hallar las aristas paralelas.

Solución

  1. El conjunto de vértices es:

    V = { v1, v2, v3, v4}

  2. El conjunto de aristas es:

    E = { e1, e2, e3, e4, e5}

  3. No hay vértices aislados.


  4. e5 es el único lazo.


  5. e1 y e4 son aristas paralelas.

13.2.2 Definición. Un grafo se llama grafo simple si no tiene aristas paralelas ni lazos.

Ejemplo 2

Los puentes de Konigsberg.

Este es unos de los problemas más antiguos referentes a grafos y que dio origen al estudio de esta teoría.

El pueblo de Königsberg es atravesado por el río Pregel, que tiene dos islas como lo denota el siguiente gráfico.

Las islas están unidas por un puente. La isla más grande está unida a cada orilla del río por dos puentes y la más pequeña sólo por uno. Hay siete puentes en total. La gente de ese pueblo se pregunta si es posible caminar por cada puente una sola vez, si se empieza en una de las orillas o en una de las islas, y regresar al punto de partida.

Solución

Este problema equivale al siguiente:

Sean cada masa de tierra un vértice y cada puente una arista. Se obtiene, el siguiente grafo:

Leonardo Euler (1707–1783) demostró que es imposible hacer un recorrido completo comenzando en cualquiera de los vértices A, B, C, D y recorriendo cada arista una sola vez y regresar al vértice del cuál se partió.

Cuando se defina lo que es un circuito euleriano en la sección 13-4 se dará una razón matemática de esta imposibilidad.

Ejemplo 3

Las redes de computadoras y de rutas de transporte, se pueden representar por medio de grafos. La inspección o análisis de sus grados, determina, por lo general, las aristas de unión con fines de optimización.

El siguiente es un grafo de las carreteras entre Medellín y Bogotá.

13.2.3 Definición. Sean G un grafo y v un vértice de G. El grado de v, denotado por grad (v), es el número de aristas que salen de v. Una arista que vea un lazo, se cuenta dos veces.

Ejemplo 4

Dado el siguiente grafo, encuentre el grado de cada vértice.

Solución

grad (v1) = 3, grad (v2) = 3

grad (v3) = 4, grad (v4) = 0

13.2.4 Teorema. Sea G un grafo con vértices v1, v2,..., vn. Entonces la suma de los grados de todos los vértices de G es igual a dos veces el número de aristas en G. Es decir,

grad (v1) + grad (v2) + ………+ grad (vn) = 2 A, donde A es el número de aristas de G.

Demostración

Dados los vértices vi y vj pertenecientes a G, eventualmente una a estos dos vértices, suma 1 al grado de vi y 1 al grado de vj y por tanto 2 a:

Así, 2A es el total de la suma de los grados de los vértices de G.

Como consecuencia del teorema anterior se tiene que para cualquier grafo, el número de vértices de grado impar, debe ser par.

Ejemplo 5

¿Es posible tener un grafo, en el que cada vértice tiene grado 4 y hay 10 aristas?.

Solución

Por el teorema anterior se tiene:

2A = 20 o sea que deben existir 10 aristas.

De otra parte, como los vértices tienen el mismo grado 4, se debe cumplir que, 20=4 V, donde V es el número de vértices. Por tanto V = 5.

La figura siguiente muestra uno de eso grafos:

Ejemplo 6

¿Se puede dibujar un grafo G con tres vértices v1 v2 y v3, donde,

  1. grad (v1) = 1, grad (v2) = 2, grad (v3) = 2
  2. grad (v1) = 2, grad (v2) = 1, grad (v3) = 1
  3. grad (v1) = 0, grad (v2) = 0, grad (v3) = 4

Solución

  1. No es posible porque la suma de los grados de los vértices es 5 que el un número impar.

  2. Sí, porque grad (v1) + grad (v2) + grad (v3) = 4; que es un número par. El número de aristas es 2.

    No existen otros grafos que cumplan estas condiciones.

  3. Sí, porque grad (v1) + grad (v2) + grad (v3) = 4; que es un número par. El único grafo es:

13.2.5 Definición. El grafo completo de orden n, que se denota por kn, es el grafo que tiene n vértices y cada vértice está unido a los demás por exactamente una arista.

Ejercicios 13.2

  1. Dibuje todos los grafos simples que tienen dos vértices.

  2. Dibuje todos los grafos simples que tienen cuatro vértices y seis aristas.

  3. Sea G un grafo con vértices v1, v2, v3, v4, v5, v6 de grados 1, 2, 3, 4 y 5 respectivamente.

    ¿Cuántos aristas tiene G? Justifique su respuesta,

  4. ¿Se puede dibujar un grafo simple con vértices v1, v2, v3, v4 de grados 1, 2, 3, 4 respectivamente? Justifique su respuesta.

  5. Dibujar los grafos completos de orden 1, 2, 3, 4, 5.

  6. ¿Cuántas aristas tiene el grafo completo de orden 6? Justifique su respuesta.