Teoría de los grafos

Índice

Portada Índice
o o o o o o ........................................................................... ............................................................................................... ...................................................................................
2

3 6 8........................................................................................................... 15 ...................................................................................................................................... 16 ........................................................................................................................................ 18
19

Bibliografía

2

Teoría de Grafos
Elementos y Características de los grafos.
Losgrafos son estructuras discretas compuestas por puntos (llamados vértices) y líneas (llamadas aristas) que conectan algunos pares de esos puntos. Son una abstracción útil para modelar diversas situaciones reales como por ejemplo: redes de computadoras, redes telefónicas o eléctricas, circuitos eléctricos, sistemas de carreteras, sistemas de transporte y distribución de mercancías y sistemasorganizacionales.

Definición 1.1.1. Un grafo simple es un par G = (V, E) donde V es un conjunto nito no vacío de elementos llamados vértices y E es un conjunto de pares no ordenados de elementos distintos de V llamados aristas. Por razones técnicas se supondrá que V ∩ E = ∅. Si e = {u, v } es una arista entonces se dice que los vértices u y v son los extremos de e. Un vértice y una arista sonincidentes si el vértice es uno de los extremos de la arista. Dos vértices u y v son adyacentes si {u, v } es una arista. El orden de un grafo G = (V, E) es el número de vértices |V |. Lamentablemente en teoría de grafos no hay una terminología uniforme y aceptada por todos. Casi puede decirse que cada autor tiene su propia terminología, y por eso la mayoría de las obras sobre grafos comienzan def iniendo los conceptos que se van a utilizar. En particular, los vértices de un grafo también son llamados nodos o puntos y las aristas líneas, arcos o ejes. Un grafo se representa por medio de puntos o pequeños círculos, que designan vértices, y líneas que los unen, que representan las aristas. Para simplificar la notación frecuentemente designaremos una arista {u, v } simplemente como uv. Ejemplo1.1.2. Sea V = {a, b, c, d, e} y E = {ab, bd, be, de . Entonces (V, } es un grafo con cinco E) vértices (a, b, c, d y e) y cuatro aristas (ab, bd, be y de). La gura 1.1 es su representación grá ca:
a b

d c e

Figura 1.1: Grafo simple.

3

Definición 1.1.3. El grado de un vértice v de un grafo es el número g(v) de aristas incidentes con él. Si g(v) = 0 se dice que v es un vértice aislado.En el grafo del ejemplo anterior se tiene g(a) = 1, g(b) = 3, g(d) = g(e) =2 y g(c) = 0 (c es un vértice aislado). La sucesión de grados de un grafo se obtiene ordenando en forma no decreciente los grados de todos los vértices. En el ejemplo anterior la sucesión de grados es 0, 1, 2, 2, 3. Teorema 1.1.4 (Euler). En todo grafo G = (V, E) se cumple X g(v) = 2|E |.
v ∈V

Demostración. Las aristasse pueden contar viendo cuántas son incidentes con cada vértice y sumando todos los números obtenidos. Pero así cada arista resulta contada dos veces, una por cada uno de sus extremos. Corolario 1.1.5. En todo grafo G = (V, E) el número de vértices de grado impar es par. Definición 1.1.6. Dos grafos G = (V, E) y G0 = (V 0 , E 0 ) son isomorfos si existe una biyección f : V → V 0 que preserva larelación de adyacencia, es decir tal que

{u, v } ∈ E

si y sólo si {f (u), f (v)} ∈ E 0 .

Para indicar que G y G0 son isomorfos se escribe G ≈ G0 . Ejemplo 1.1.7. Los dos grafos representados en la gura 1.2 son isomorfos, ya que la función f que lleva a en a0 , b en b0 , c en c0 y d en d0 es una biyección y preserva la adyacencia. a b b’

c

d

a’

c’

d’

Figura 1.2: Grafos...