Grafo

Tema
3

Grafos

4.1.- DEFINICIONES BÁSICAS

Un grafo G es un par (V,E) donde V es un conjunto (llamado conjunto de vértices) y E un subconjunto de VxV (conjunto de aristas).

Gráficamente representaremos los vértices por puntos y las aristas por líneas que los unen.

Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente 2 vértices.

Llamaremosorden de un grafo a su número de vértices, |V|.

Si |V| es finito se dice que el grafo es finito. En este curso estudiaremos los grafos finitos, centrándonos sobre todo en grafos no dirigidos. También supondremos, a no ser que se diga lo contrario, que entre dos vértices hay, como mucho, una arista y que toda arista une dos vértices distintos.

Aristas

Si la arista carece de dirección sedenota indistintamente {a,b} o {b,a}, siendo a y b los vértices que une.

Si {a,b} es una arista, a los vértices a y b se les llama sus extremos.

Vértices

Dos vértices v, w se dice que son adyacentes’ si {v,w}(A (o sea, si existe una arista entre ellos)

Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es ‘par’ o ‘impar’ según lo sea sugrado.

Caminos

Sean x, y ( V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso
- x e y se llaman los extremos del camino
- El número de aristas del camino se llama la longitud del camino.
- Si los vértices no se repiten el camino se dice propio o simple.
- Si hay un camino no simple entre2 vértices, también habrá un camino simple entre ellos.
- Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
- Llamaremos ciclo a un circuito simple
- Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo

Ejemplos de Grafos

1.- Grafo regular: Aquel con elmismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.
Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular

2.- Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafossiguientes el primero es bipartito y el segundo no lo es

3.- Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.

A continuación pueden verse los dibujos de K3, K4, K5 y K6

Todo grafo completo es regular porque cada vértice tiene grado |V|-1 al estar conectado con todos los otros vértices.

Un grafo regular no tiene por quéser completo.

4.- Un grafo bipartido regular se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.

A continuación ponemos los dibujos de K1,2, K3,3, y K2,5

4.2.- PRIMEROS RESULTADOS SOBRE GRAFOS

Proposición.- La suma de los grados de los vértices es igual al doble del número de aristas

Demostración
Al realizar la suma de los grados de todos los vértices,como cada arista tiene 2 extremos se cuenta exactamente 2 veces. Por tanto la suma de los grados de los vértices es igual al doble del número de aristas

Definición (matriz de adyacencia de un grafo)
Sea G un grafo de orden n. Llamaremos matriz de incidencia de G a la matriz nxn que llamaremos A = (aij) donde aij = 1 si {i,j}(A y aij = 0 en otro caso.

La matriz de adyacencia siempre essimétrica porque aij = aji

Ejemplo:

Teorema.- Sea G un grafo de n vértices con n > 1 y sea A su matriz de adyacencia. Se cumple que el valor del coeficiente [pic]de la matriz [pic] es igual al número de caminos de longitud k con extremos vi y vj

Demostración
Por inducción en k
Para k = 1 es la definición de A
Supongamos que es cierto para k y vamos a verlo para k+1.
La casilla...