Grafos y Árboles: Definiciones y Propiedades

Grafos

Se llama Grafo a la terna G = (V, A, φ), donde V es un conjunto finito no vacío de vértices, A es un conjunto finito de aristas, donde cada arista está asociada a un conjunto compuesto por 2 vértices extremos. La función φ de incidencia le hace corresponder a cada arista sus vértices extremos de V. ∀x∈A: φ(x) = {vi, vj}

Defs

Def 1: Un vértice y una arista son incidentes si y solo si el vértice es extremo de la arista.

Def 2: 2 aristas son paralelas (o múltiples) si los vértices asociados a cada una de ellas coinciden.

Def 3: Una arista es un lazo (o bucle) si sus extremos coinciden.

Def 4: El grado o valencia de un vértice es el número de aristas que inciden en él.

Def 5: Un vértice v se dice aislado si g(v) = 0. Es decir, no incide ninguna arista en él.

Def 6: Un vértice v es un vértice pendiente si g(v) = 1.

Def 7: 2 vértices son adyacentes si son extremos de una misma arista.

Def 8: 2 aristas son adyacentes si tienen un vértice en común.

Def 9: Si todos los vértices de un grafo tienen el mismo grado, el grafo se dice regular. Si todos los vértices tienen grado k, el grafo es k-regular.

Def 10: Un grafo se llama simple (o sencillo) si no tiene lazos ni aristas paralelas.

Def 11: Matriz de incidencia de grafos. Sea (V, A, φ) un grafo de n vértices y k aristas. Entonces |V| = n, el número de elementos de V es n y |A| = k, el número de elementos de A es k. Se llama matriz de incidencia de un grafo (V, A, φ) (que no tenga lazos) a una matriz Mi = ||mij|| de n filas y k columnas, tal que mij = {1 si… 0 si… Cada columna de una matriz de incidencia tiene 2 unos. La suma de los elementos de cada fila da el grado del vértice correspondiente. Cuando estamos en presencia de lazos, en las columnas tendríamos un solo 1.

Def 12: Matriz de adyacencia de vértices de un grafo. Es una buena representación para grafos sin aristas paralelas. Sea G = (V, A, φ) un grafo de n vértices. Se llama matriz de adyacencia de vértices de un grafo a una matriz Mv = ||mij|| de orden n x n tal que mij = {1 si v y v son adyacentes, 0 en todo otro caso. Esta matriz también se puede utilizar aún en presencia de aristas paralelas o múltiples haciendo la siguiente salvedad. Se coloca el número de aristas paralelas entre los vértices involucrados.

Teorema del saludo de manos

Sea G = (V, A, φ) un grafo, la suma de los grados de todos los vértices del grafo es igual al doble del número de aristas. V = {vi} |V| = n |A| = k -> Σg(vi) = 2*|A|

Corolario: El grado total de un grafo es par.

Teorema

En todo grafo hay un número par de vértices de grado impar.

Demost: Sea V el conjunto de vértices de un grafo. Sea Vp el conjunto de los vértices de grado par. Vp = {vp} Sea Vi el conjunto de los vértices de grado impar. Vi = {vi} V = Vp ∪ Vi -> Σg(vj) = 2|A| La suma de los grados de todos los vértices es igual a la suma de los grados de los vértices de grado par más la suma de los grados de los vértices de grado impar. Σg(vp) es un número par porque es la suma de números pares. 2|A| es un número par porque es múltiplo de 2. En consecuencia, Σg(vi) debe ser par. Pero g(vi) es una suma cuyos términos son todos impares. Si el resultado de esta suma es par, entonces el número de términos de esa sumatoria debe ser par. Por lo tanto, el número de vértices de grado impar es par, que es lo que queríamos demostrar.

SUBGRAFOS

Una terna S = (V’, A’, φ’) es un subgrafo del grafo G = (V, A, φ) si se cumple: I) V’ ⊂ V II) A’ ⊂ A III) φ’ es una restricción de φ en A’.Subgrafo restante respecto de un vértice: Se llama subgrafo restante respecto del vértice vi al grafo obtenido a partir del grafo original omitiendo el vértice vi y todas las aristas que inciden en él. Se simboliza Gvi. Subgrafo restante respecto de una arista: Se llama subgrafo restante respecto de una arista ai al grafo que se obtiene suprimiendo la arista ai del grafo original y que se simboliza: G~a Subgrafo generado por un subconjunto de vértices W: Sea W un subconjunto de vértices de V. Se llama subgrafo generado por un subconjunto de vértices W al grafo que tiene a W como subconjunto de vértices y cuyo conjunto de aristas está formado por todas las aristas del grafo original que tienen ambos extremos en W.

Conexión de Grafos Camino

Sea G un grafo G = (V, A, φ) y sean vi y vj 2 vértices de G. Un camino de vi a vj es una sucesión finita alternada de vértices adyacentes y aristas de G. Un camino trivial de v1 a v1 consiste del único vértice v1. Un camino puede iniciar y terminar en el mismo vértice, puede repetir aristas y vértices. Cadena: Dado un grafo G = (V, A, φ) se llama cadena a una sucesión alternada de vértices adyacentes y aristas de la forma v1 a1 v2 a2 v3 a3 … an vn que comienza y termina en vértice y que cumple las siguientes condiciones: i) Las aristas son todas distintas. ii) Cada arista incide en el vértice precedente y en el siguiente. Cadena simple: es una cadena en la cual todos los vértices son distintos. Ciclo: Un ciclo es una cadena cuyo vértice inicial coincide con el final. Ciclo simple: es un ciclo en el que no se repite ningún vértice, salvo el primero (y el último) Longitud de un camino: Se llama longitud de un camino (o cadena o ciclo) al número de aristas que la componen. Número de caminos entre 2 vértices: se puede determinar usando su matriz de adyacencia de vértices. T: Sea G un grafo y sea MG su matriz de adyacencia con respecto a la ordenación v1, v2, v3,…, vn (se admiten aristas múltiples o lazos). El número de caminos distintos de longitud r de vi a vj, siendo r un entero positivo, es igual al elemento en la posición (i, j) de la matriz MG^r.

Conectividad

Un grafo está conectado si es posible viajar desde cualquier vértice a cualquier otro vértice a lo largo de una sucesión de aristas adyacentes del grafo. Grafo Conexo: Sea G un grafo. 2 vértices vi y vj de G son conexos si y solo si existe un camino de vi a vj. El grafo G es conexo si, dados 2 vértices cualesquiera vi y vj de G, hay un camino de vi a vj. Lema: Sea G un grafo a) Si G es conexo, entonces 2 vértices distintos cualesquiera de G pueden conectarse con una cadena simple. b) Si los vértices v y w forman parte de un ciclo en G y se quita una arista del ciclo, entonces aún existe una cadena de v a w en G. c) Si G es conexo y contiene un ciclo, entonces se puede eliminar una arista del ciclo sin desconectar a G.

Grafo no conexo

Teo: Un grafo G = ( V, A , φ) q no es conexo , es la unión d 2 o + subgrafos conexos q 2 a 2, no tienen ningún vért en común. A estos subgrafos conexos disjuntos s les llama componentes conexas dl grafo. Desconexión d Grafos Punto de corte: Un vért v d un grafo conexo G es un istmo o punto d corte sii el subgrafo restante respecto d v es no conexo. Puente: Una arist a d un grafo conexo G es un puente si el subgrafo restante respecto d esa arist es no conexo.

Ciclo d Euler: Un ciclo en un grafo G = ( V , A , φ ) es un ciclo d Euler si recorre todas las arist dl grafo en estudio. Teo: Un grafo conexo G admite un ciclo d Euler sii todos sus vértices tienen grado par. Teo: Un grafo conexo G contiene una cadena d Euler sii tiene exactamente 2 vértices d grado impar, siendo todos los demás vértices d grado par.

Ciclo d Hamilton: Sea un grafo conexo G = (V, A, φ) tiene un ciclo de Hamilton si existe un ciclo simple d G q contenga todos los vért d V. Una cadena d Hamilton es una cadena simpl d G q contien todos los vért. Sugerencias p/intentar hallar un ciclo d Hamilton según Grimaldi. En un grafo G = (V, A, φ) : 1) Si G tiene un ciclo d Hamilton, entonces p/ v € V, grad (v) ≥2. 2) Si v €V y grad (v) = 2, entonces las 2 arist incidentes en el vértice v deben aparecer en cualkier ciclo de Hamilton d G. 3) Si v €V y grad (v) > 2, entonces cuando se intenta construir un ciclo de Hamilton, una vez q se pase x v, las arist no utilizadas incidentes en v s dejan d tener en cuenta.

GRAFOS ISOMORFOS Dados 2 grafos G = (V, A, φ) y G = (V,A,φ) se dice q G y G son isomorfos si existe una f biyectiva f : V → V y una f biyectiva g : A → A q conserven las relaciones d incidencia y adyacencia. Invariante del isomorfismo: Una prop P se llama invariante dl isomorfismo dl grafo, sii, dados 2 grafos cualeskiera G y G , si G tiene la prop P y G es isomorfo a G, entonces G tiene la prop P. Teorema: C/u d las sig prop es un invariante dl isomorfismo dl grafo, dónde, n, m y k son todos enteros no negativos. 1) Tiene n vértices 2) Tiene m aristas 3) Tiene un(m) vértice d grado k 4) Tiene un ciclo d long k 6) Tiene un(m) ciclo simpl d long k 8) Es conexo 9) Tiene un ciclo d euler 10) Tiene un ciclo d Hamilton.

Tipos especiales d grafos Grafos k-regulares El grafo regular d grado k o grafo k-regular es aquél en el q todos los vért tienen grado k. Los grafos k regulares pueden ser simples o no. Grafo Completo d p vértices: s simb Kp es un grafo simple cuyo conj d vértices tiene p elementos y tal q todo par d vért distintos determina una arist. O lo q es lo mismo: un grafo simple es completo si todo vért está conectado con todo otro vért. Prop dl Grafo Completo KP 1) Todo vért tiene grado p – 1. 2) El subgrafo restante d Kp respeto d cualkiera d sus vért es isomorfo con Kp – 1. 3) Dados 3 vért  d Kp ( p ≥3 ) existe un ciclo d long 3 q los contiene sólo a ellos. 4) Para p ≥3 , Kp es un bloque es decir q carece d itsmos y puentes 5) Si A es el conj d aristas d Kp entonces |A|=C p,2. 6)Un grafo completo Kp siempre tendrá un ciclo hamiltoniano, cuando p ≥ 3, Grafo Complementario: Dado un grafo simple G = ( V , A , φ ) se llama grafo complementario d G al grafo G = (V, A’ ,φ’) q tiene el mismo conj d vért q G y cuyas aristas son justamnt las q le faltan a G p/ser completo. Grafos bipartitos: Un grafo simple G s dic bipartito si su conj d vért s puede particionar en 2 subconj V1 y V2 tales q toda arista dl grafo conecta un vértice d V1 con un vértice d V2. Recordemos q V1 y V2 forman una partición d V sii V1 u V2 =V y V1 n V2 =0. Grafo Bipartito Completo: Un grafo simple es bipartito completo cuando es bipartito y ad+ cada vért d V1 está conectado con cada vért d V2 Un grafo bipartito completo s denota Kp,q (o tmb Kn1;n2) donde el 1er subíndice es el nro d elementos d V1 y el 2do subíndice es el nro d elementos d V2. En gral se acepta q siempre sea p≤ q .

GRAFO PLANAR (GRAFO PLANO): Un grafo es plano si puede dibujars en el plano d manera q ningún par d sus aristas s corte(x corte d aristas s entiende la intersección d las líneas q representan a las aristas) en un pto  d sus vértices.

Mapa Se llama mapa a una rep plana particular d un grafo plano finito. El mapa es conexo si el corresp grafo es conexo. Un mapa dado divide el plano en varias regiones y tmb s presenta una región sin frontera, es decir no acotada. Así no hay pérdida d generalidad al contar las regiones si suponemos q nuestro mapa está contenido en algún rectángulo mayor en lugar d en el plano completo. Frontera d una región: Sea un grafo plano G, al conj d vért y arist q inciden en una región r d G s le llama la frontera d r.

Teo d Euler p/grafo plano conexo Si G es un grafo plano conexo con | V |= nº d vért, | A |= nº d arist y q descompone al plano en r regiones entonces s cumple q | V | – |A| + r = 2  P/Grafo plano no Conexo Si G es un grafo plano no conexo se cumple | V | – | A | + r = ν + 1 donde ν es el nro d comp conexas.

Teo d Kuratowski: Un grafo es plano sii, no contiene ningún subgrafo isomorfo a K5 ni a K3,3 ni a subdivisiones d ellos.

Grafos coloreados El coloreado d un grafo G=(V,A,φ) es una asignación d colores a los vért d G d tal forma q vért adyacentes tengan colores distintos. Se dice q G es n-coloreable si existe un coloreado d G q usa n colores. Nro cromático: es el nro mín d colores necesario p/colorear G. Y se utiliza la letra griega chi p/rep χ(G), Si coloreamos un grafo completo χ(Kp)=p, necesitamos 2 colores p/colorear un grafo bipartito. Grafos planares y coloreado Teorema: Cualkier grafo planar G es 5-coloreable. Teorema d los 4 colores: Si las regiones d un mapa M se colorean d forma q las regiones adyacentes tengan colores distintos, entonces no se necesitan + d 4 colores.

Grafos rotulados o ponderados Un grafo G se llama un grafo rotulado o ponderado si sus arist y/o vért s le asignan datos d alguna clase. En particular, si a cada arist a d G se le asigna un nro no neg entonces a l(s) s le llama el peso o long l(s) d a.

Se llama dígrafo o grafo dirigido a una terna D = (V, A,δ) dónde V es un conj d vért, A es un conj d arcos y δ es una f q a cada elemento d A le hace corresponder un elemento d V x V. ¥ x €A: δ (x) = (vi, vj )

Arcos estrictamente paralelos: 2 arcos d un dígrafo son estrictamente paralelos si tienen el mismo vért inicial y el mismo vért final. Rizo: Un arco es un rizo, si tiene inicio y final en el mismo vért. Dígrafo sencillo: si no tiene rizos ni arcos estrictamente paralelos. Grado neg d un vért: se simb g – (v) y es nro d arcos q llegan a ese vért. Grado posit d un vért: se simb con g + (v) y es nro d arcos q parten d s vért  Grado total d un vért: es la + d su grado neg y su grado posit. gt(vi) = g – (vi) + g+ (vi)  Grado neto d un vért: nro entero q resulta d – el grado posit y el grado neg d s vért. gn(vi) = g+ (vi) – g – (vi)  

 Prop: Σg^–(v)=Σg+(v)=|A|; Σgt(v)=2|A|; Σgn(v)=0

Dígrafos Isomorfos Sean D = (V, A, δ ) y D´ = (V´, A´, δ´) 2 dígrafos D y D´ son dígrafos isomorfos si sus respectivas estructuras d grafo subyacentes son isomorfas y ad+ subsist la orientación d los arcos homólogos.

tipos d conexidad.: Dígrafos débilmnt conexos: Un dígrafo es débilmnt conexo si p/todo par d vértices d V, existe una cadena q los une. En otras palabras, un dígrafo es débilmnt conexo si el grafo subyacent es conexo. Dígrafos Unilateralmnt conexos: Un dígrafo sin arcos estrictamente paralelos s dic q es unilateralmnt conexo si p/todo par d vértices vi y vj dl dígrafo existe al menos un cadena q parte d vi a vj o d vj a vi . En otras palabras, si p/todo par d vértices existe al menos un cadena q parte d una d ellos y llega al otro. Dígrafos Fuertemnt conexos: Un dígrafo es fuertemnt conexo si p/todo par d vértices vi , vj d V existe una cadena d vi a vj y una cadena d vj a vi

Rep Matricial d Dígrafos 1) Matriz d Incidencia d Dígrafos; Es una buena rep si el dígrafo no tiene rizos Def: Sea D = (V, A,δ ) un dígrafo dónde |V|= n y |A| = k . Se llama matriz d incidencia a una matriz M_i^n*k =||mij|| d orden nxk/ mij{ 1 si aj sale d vi, -1 si aj llega a vi, 0 en otro caso}  La + d los elementos d una fila es = al grado neto dl vért respectivo. Se puede utilizar si posee rizos, s coloca en la pos dl vért inicial y final ± p/indicar la presencia dl rizo. 2) Matriz d Adyacencia d vért en un Dígrafo Es una buena rep si el dígrafo no tiene arcos estrictamente paralelos. Sea D = (V, A,δ ) un dígrafo d n vértices. Se llama matriz d adyacencia d vértices a una matriz cuadrada d orden n / Mv = ||mij ||d orden n x n tal q mij = {0 en todo otro caso 1 si hay un arco de vi a vj} Se puede utilizar en presencia d arcos estrictamente paralelos o múltiples colocando en los vértices involucrados el nro correspondiente d aristas q haya

Sumidero: es un vért al q sólo llegan arcos. El g+ (v) = 0.  Fuente: es un vért dl q sólo parten arcos. No hay ningún arco q llegue a él. El g- (v) = 0

Árboles: Se llama árbol a un grafo conexo y acíclico. Al ser acíclico no admite lazos, ni arist paralelas. Def equiv: Todo par d vért d G está conectado x una única cadena, G es acíclico pero si s le agrega una arista aparece un ciclo único; G es conexo si bien todas sus aristas son puentes.  Árbol con Raíz: Un árbol con raíz consta d un grafo árbol con un vért designado como raíz dl árbol. Todo árbol puede constituirs en un árbol con raíz simplemnt escogiendo uno d los vérti como raíz. Nivel d un vértice v d un árbol con raíz r a la long d la única cadena q va d r a v Altura d un árbol: Se llama altura d un árbol al máx nivel dl árbol Hojas o vért terminales: vért pendientes dl arbol Vért internos: Se llaman vért internos a todos los vért q no son terminales. La raíz es vért interno.

Arboles genealógicos: Antepasados o antecesores: El vert vi es antepasado de vj si la unica cadena q une a vi con la raiz incluye a vi.  Hijos: Un vert vi es hijo d vj o vj es padre d vi si: 1) vi sigue a vj 2) vi es adyacente a vj. Todo vért (excepto la raíz) es hijo d un solo vért, pero puede ser padre d varios. Hermanos: si vi y vj tienen el mismo padre. Descendientes d un vért: Los descendientes dl vértice v, son todos los vért q se encuentran x debajo d ese vért en el árbol

Subárbol D la propia estructura d árbol surge q todo vért es raíz d un subárbol contenido en el árbol original. Si en el árbol original borramos la raíz y las aristas q la unen con los vért d nivel uno obtenemos árboles disjunto es decir un bosque. Estos bosques tienen la prop d q c/u d sus componentes conexas es un árbol.

Se llama Árbol con raíz ordenado a un árbol con raíz en el cuál se prescribe un orden p/los vértices d cada nivel. Tales árboles se dibujan con la raíz R en la parte sup y las aristas dirigidas hacia abajo y los hijos ordenados d izq a der. Sistema universal d direcciones: el orden se denomina orden lexicográfico u orden d diccionario.

Árbol m–ario Siendo m un entero positivo, s dice q un árbol con raíz es un árbol m – ario si cada vért int tiene a los sumo m hijos. Árbol m -ario completo Si todos los vértices internos d un árbol con raíz tienen exactamnt m hijos, se llama árbol m –ario completo.

Prop: T1: Un árbol d n vért tiene n-1 arist. T2: Los árboles son 2-coloreables. T3: Un árbol m-ario completo con i vértices internos tiene n= mi+1 vértices y l(hojas)=(m-1)i+1. T4: Un arbol m-ario completo d altura h tiene a lo sumo m^h hijos.Árbol m –ario posicional Son árboles m –arios en los cuales los hijos d cada vért ocupan pos distintas.

Árbol binario posicional: Es un árbol con raíz en el cuál cada vért int tiene un hijo a la der y/o un hijo a la izq o bien, ningún hijo. Árboles Etiquetados Casi siempre conviene etiquetar los vért o las aristas d un grafo p/indicar q se usarán p/un propósito particular. Árboles Binarios Posicionales q rep Exp Alg: Las op fund: +, -, * y / son operaciones binarias y se pueden rep x árboles binarios etiquetados.En este árbol, la raíz s etiqueta con el op central d la exp dada. Los 2 hijos d la raíz se etiquetan con los op d los arg izq y der respectivamente. Si algún arg está constituido x una cte o una var, el hijo corresp s etiqueta con esa cte o var.

 Análisis o recorrido d un árbol es el proceso d visitar cada vértice dl mismo exactamnt una vez en algún orden específico. Se estudian 3 formas d recorrerlo: Orden inicial( preorden, prefija o notacion polaca)(RID), orden intermedio(IRD) y orden final(IDR)