Cbvcb

Los problemas que aparecen en este curso son mayormente formulados mediante grafos. Este capitulo esta dedicado al concepto de grafo.


Definiciones


Multigrafo Un multigrafo G=(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).

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 que no tiene ramas multiples ni bucles. Por ejemplo,
Nota: En adelante consideraremos sólo grafos. Cuando se trate de unmultigrafo 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 de un vertice El grado de un vertice u, escribiremos grad(u), es el numero de ramas que tienen a u como extremo. Decimos que lasramas 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(= [pic]. Por ej. la figura 2 es un K4 si se agregara la rama (2,4).

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 indicacionen contrario los caminos que consideraremos son simples. Si el camino incluye a todos 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 o ciclo, 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 tienealgun circuito hamiltoniano decimos que el grafo es hamiltoniano.




Dodecaedro: ejemplo de grafo 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 un extremo en M y otro en N. Decimos que G es completo sipara 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 Un grafo 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 unsubconjunto 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) es rama 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 elgrafo que resulta de G suprimiendo las ramas R.


Grafo dirigido o digrafo Un grafo dirigido o digrafo G=(V,D) esta formado por un conjunto de vertices V y un subconjunto D de pares ordenados de vertices que llamamos arcos. Por ejemplo,


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 circuitodirigido.

Arbol Un grafo aciclico y conexo se llama arbol.




Arbol con raiz 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...