Primer Parcial 18/07/2003 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia


1)
Sea C el camino orientado mas largo de G. Por HI, todo vertice tiene un grado de entrada positivo, con lo cual el vertice inicial del camino debe provenir de otro vertice. Este vertice debe estar en C, ya que de lo contrario se extenderia el camino (y no seria el mas largo ABS), con lo cual de esta forma se cierra un circuito orientado. Se puede probar analogamente para vertices de grado de salida positivo


2)
a)Sup. no hay un vertice adyacente a todos. Como G no puede contener como subgrafo inducido a un camino simple/circuito simple de 4 nodos, si se recorre por BFS partiendo de un nodo (sea v0) no se podra llegar a mas de 2 niveles (si se puede llegar, se estarian formando caminos de 4 nodos) y tampoco de menos de 2 (si se llega a 1 -> todos eran adyacentes a v0 -> ABS). En este caso desde v0 se puede llegar a un camino de 3 vertices, con lo cual ni v0 ni los vertices del ultimo nivel tendran mas adyacentes -> el resto de los vertices deberan estar conectados a v1 (el adyacente a v0). Pero esto significa que v1 es adyacente a todos -> ABS (Si no se entendio o esta mal o incompleto avisenme)

b)Supongamos G no conexo -> vale G no conexo -> listo

Supongamos G conexo ->

-> Por a) tiene un vertice adyacente a todos los otros

-> G complemento tendra un vertice que no sera adyacente a ninguno (por def de complemento)

-> G complemento no conexo -> listo


3)
a) El mayor numero de ejes que puede tener un grafo sin circuitos es n-1, es decir ser un arbol, ya que cualquier eje que se le agregue formara un ciclo
b) El mayor numero de ejes que puede tener un digrafo sin circuitos es n(n-1)/2, es decir uno con el subyacente completo, ya que todos se pueden orientar a un mismo sentido


4)
5)