Hola

Gregorio Hernández Peñalver Departamento de Matemática Aplicada, Facultad de Informática, UPM

Matemática Discreta

TEMA 4 GRAFOS
NOCIONES BÁSICAS
Un grafo es un par G=(V,A), donde V es un conjunto finito no vacío (a cuyos elementos llamaremos vértices) y A es una familia finita de pares no ordenados de vértices de V (a cuyos elementos llamaremos aristas o arcos). Un grafo simple es un parG=(V,A) donde V es un conjunto finito no vacío y A es un conjunto finito de pares no ordenados de vértices distintos de V. Si a={u,v} es una arista de G escribiremos sólo a=uv, y diremos que a une los vértices u y v o que u y v son extremos de a. Una arista a=uu se llama bucle. Una arista que aparece repetida en A se llama arista múltiple. (En otros textos llaman grafo al que aquí se denominagrafo simple, permitiendo la presencia de aristas múltiples en los multigrafos y de bucles en los seudografos). Dos vértice son adyacentes si son extremos de una misma arista. Dos aristas son adyacentes si tienen un extremo común. Un vértice y una arista son incidentes si el vértice es extremo de la arista. Un vértice es aislado si no tiene otros vértices adyacentes. Un grafo completo es un grafosimple en el que todo par de vértices está unido por una arista. (Se representa con Kn al grafo completo de n vértices). Un grafo G=(V,A) se llama bipartido si existe una partición de V, V=X∪Y, tal que cada arista de G une un vértice de X con otro de Y. (Se designa por Kr,s al grafo bipartido completo en que ⏐X⏐= r e ⏐Y⏐= s, y hay una arista que conecta cada vértice de X con cada vértice de Y) Dosgrafos G=(V,A) y G’=(V’,A’) son isomorfos si existe una biyección f:V→V’ que conserva la adyacencia. (Es decir, ∀ u,v∈V, u y v son adyacentes en G ⇔ f(u) y f(v) son adyacentes en G’. Un subgrafo de G=(V,A) es otro grafo H=(V’,A’) tal que V’⊆V y A’⊆A. Si V’=V se dice que H es un subgrafo generador. GRADO Se llama grado de un vértice v al número de aristas que lo tienen como extremo, (cada bucle secuenta, por tanto, dos veces). Se designa por d(v) Un grafo regular es un grafo simple cuyos vértices tienen todos el mismo grado. A la sucesión de los grados de los vértices de G se le denomina sucesión de grados del grafo G. Una sucesión de enteros no negativos se dice sucesión gráfica si es la sucesión de grados de un grafo simple. Propiedades: 1) La relación entre los grados y el número dearistas en G es: d( v) = 2 A
v∈ V

∑

2) Hay grafos no isomorfos con la misma sucesión de grados 3) La sucesión (d1,d2,...,dn) es la sucesión de grados de un grafo ⇔ Σdk es par. 4) Para grafos simples se tiene que: la sucesión no creciente (s,t1,...,ts,d1,...dr ) es gráfica ⇔ lo es la sucesión (t1 −1,...,ts −1,d1,...dr ) MATRICES Y GRAFOS La matriz de adyacencia de un grafo G con n vértices{v1,...,vn} es la matriz nxn , M(G)=(aij), donde aij es el nº de aristas que unen vi con vj. La matriz de incidencia de un grafo simple G con n vértices {v1,...,vn} y k aristas {e1,...,ek} es la matriz nxk, I(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario.

1

Gregorio Hernández Peñalver Departamento de Matemática Aplicada, Facultad de Informática, UPM

MatemáticaDiscreta

CAMINOS Y CONEXIÓN Un recorrido en un grafo es una sucesión de vértices y aristas de la forma v0 a1 v1 a2...vk-1 ak vk donde la arista ai une los vértices vi-1 y vi. Éste es un recorrido de v0 a vk, de longitud k, siendo v1,...,vk-1 los vértices interiores del camino. Si v0=vk decimos que el recorrido es cerrado (en ocasiones se le llama circuito). Un camino en un grafo es un recorrido en elque no se repiten vértices ni aristas. Un ciclo es un camino cerrado. Propiedades: 1) El nº de recorridos de longitud k de vi a vj es el elemento ij de la matriz M(G)k. 2) Un grafo G es bipartido ⇔ G no tiene ciclos de longitud impar. 3) Si G tiene sólo dos vértices impares existe un camino entre ellos.

Un grafo es conexo si para cada par de vértices u y v existe un camino de u a v. Si G es...