¿Un Grafo? ¿Y eso que es?
Podemos clasificar los grafos en 2 tipos básicos, dirigidos y no dirigidos.
1. Los grafos dirigidos están formados por vértices y arcos. Los arcos son pares ordenados de vértices, es decir, A -> B, el vértice A es el primero y B el segundo, y esta unidos por un arco que marca el orden.
2. Los grafos no dirigidos están formados por vértices y aristas, que son pares de vértices no ordenados, al contrario que pasa con los arcos.
3. Podemos asociar un grafo no dirigido a uno dirigido si ignoramos la dirección de los arcos y siempre que tengan en mismo conjunto de vértices.
4. Un grafo mixto es aquel que contiene tanto arcos como aristas.
5. Los extremos de una arista o arco (los vértices) se dice que son incidentes con la arista o arco.
Los vértices A y B son incidentes con la arista e1.
6. Dos vértices que comparten una misma arista o arco, es decir, que son incidentes con esta, se dice que son adyacentes el uno con el otro.
Los vértices A y B son adyacentes.
7. Un bucle es una arista o arco cuyos extremos son el mismo vértice.
El vértice 1 tiene un bucle.
TIPOS PARTICULARES DE GRAFOS:
1. Una grafo simple es un grafo sin bucles y en el que no hay dos aristas que unan el mismo par de vértices. Si el grafo es dirigido diremos que es simple si no tiene bucles y no hay dos arcos uniendo el mismo par de vértices y con la misma dirección.
Cuando un grafo NO es simple, se le llama multigrafo.
Grafo simple
Multigrafo
Multigrafo
2. Un grafo se dice que es completo si hay al menos una arista o arco uniendo cada par de vértices distintos. A un grafo no dirigido y simple lo denominamos Kn.
Grafo completo K6
3. Un grafo no dirigido diremos que es bipartito si existe una partición {X,Y} del conjunto de vértices de forma que toda arista tiene un extremos en X y otro en Y.
Para los grafos dirigidos diremos que es bipartito si lo es su grafo no dirigido asociado.
V1={A,B,C,D,E}, V2={F,G,H,I}
TEOREMA
1. Sea G=(V,A) un grafo, entonces:
2. Sea G=(V,A) un grafo dirigido, entonces:
COROLARIO
El numero de vértices de grado impar de un grafo es par.