Dvsadv

Introducción a los Grafos
Comencemos por definir algunos términos: Grafo: Sea V un conjunto finito de elementos que llamamos vertices y sea E un conjunto de pares de vertices que llamamos ramas. Al par G=(V,E) lo llamamos grafo. Advertimos que un grafo es un multigrafo sin ramas multiples ni bucles. Por ejemplo, V={1,2,3,4} E={{1,2},{2,3},{3,4},{1,4},{1,3},{2,4}} Multigrafo: Un multigrafoG=(V,E) es una funcion que asigna a cada elemento e de E (ramas) un par no ordenado {u,v} de elementos de V (vertices) que llamamos los extremos de e. Por ejemplo,

Nota: Las ramas b y c tienen los mismos extremos (ramas multiples). Los extremos de la rama f son iguales (bucle). Nota: De ahora en adelante consideraremos sólo grafos. Cuando se trate de un multigrafo lo aclararemos explicitamente.Adyacente: Si (u,v)∈E decimos que los vertices u y v son adyacentes. Tabla de adyacencia de un grafo: Es una tabla que asigna a cada vertice u de G la lista de ramas que tienen uno de sus extremos en u.

Grado: El grado de un vertice u, escribiremos grad(u), es el numero de ramas que contienen a u como un extremo. Decimos que las ramas 'inciden' en u. Grafo completo: Si u, v ∈ V implica que (u, v) ∈E decimos que G es completo y escribimos Kn donde n =|V|. En este caso, |E|= (2n). Por ej. la figura anterior es un K4. Camino: Una sucesion de vertices u1, u2, ..., up tales que (ui,ui+1)∈E lo llamamos un camino (que une u1 con up). Si todos los ui son distintos decimos que el camino es 'simple'. Salvo indicacion en contrario los caminos que consideraremos son simples. Si el camino incluye atodos los vertices de V decimos que el camino es 'hamiltoniano'. Circuito o Ciclo: Un camino tal que u1,u2,...,up-1 son distintos y up=u1 lo llamamos un circuito, es decir, un circuito es un camino 'cerrado'. Si el circuito contiene todos los vertices de V decimos que el 'circuito es hamiltoniano'. Si G contiene un circuito hamiltoniano decimos que el grafo es hamiltoniano. Dodecaedro: ejemplo degrafo hamiltoniano.

Grafo aciclico: Un grafo que no contiene circuitos lo llamamos aciclico. Grafo Bipartito: Un grafo G=(V,E) se llama bipartito si V esta particionado en 2 subconjuntos M y N tales que toda rama de E tiene sus extremos en cada subconjunto. Decimos que G es 'completo' si para todo par u∈M y v∈N se tiene que (u,v)∈E. En este caso escribimos Kmn donde m=|M| y n=|N| Subgrafo: Ungrafo H se dice que es un subgrafo de G si todos los vertices y ramas de H son vertices y ramas de G. Grafo conexo: Un grafo es conexo si u,v∈V implica que hay un camino que une u con v. Un subgrafo H conexo y maximal de G se llama una 'componente' de G Subgrafo inducido: Sea U un subconjunto de vertices del grafo G. El grafo H cuyos vertices son U y tal que (u,v) con u,v∈U es rama en H si (u,v) esrama en G se llama grafo inducido por U. Substraccion de vertices o ramas: Sea G=(V,E) un grafo y U un subconjunto de V entonces G-U es el grafo que resulta de G suprimiendo los vertices U y las ramas que inciden sobre los vertices de U. Sea R un subconjunto de E entonces G-R es el grafo que resulta de G suprimiendo las ramas R. Grafo dirigido o digrafo: Un grafo dirigido o digrafo G=(V,D) estaformado por un conjunto de vertices V y un subconjunto D de pares ordenados de vertices que llamamos arcos. Por ejemplo, V={1,2,3,4} E={(1,2),(3,2),(4,3),(1,4),(4,1),(2,4)} En un grafo dirigido una sucesion de vertices u1, u2, ..., up tales que (ui,ui+1)∈E lo llamamos un 'camino dirigido'. Si u1 =up decimos que es un 'circuito dirigido'. Arbol: Un grafo aciclico y conexo se llama arbol. Arbol conraiz: A rooted tree es un grafo dirigido cuyo arbol subyacente es un arbol que tiene un vertice distinguido, raíz, tal que hay un solo camino dirigido de la raiz a cualquier otro vertice. Si u→v decimos que u es el padre de v y v es el hijo de u. Si v se encuentra en un camino dirigido a partir de u, decimos que v es descendiente de u. Si no existe v tal que u→v decimos que u es una hoja. Decimos...