GRAFOS CONCEPTOS Y TERMINOLOGÍA
GRAFOS
CONCEPTOS Y TERMINOLOGÍA
NOMBRES:
UCIEL MARTINEZ RODRIGUEZ - 1170266.
JONY Diaz - 1170923
ARACELI JIMENEZ PEREZ - 1220084
DANIEL HERRERA RODRIGUEZ.
DAVID GARCIA VERA- 1220234
Responde F o V según corresponda. Si es F comente porqué.
V=Todo grafo completo no tiene camino Hamiltoneano
V=Un grafo bipartito completo puede tener una clique (subgrafo completo).
F, contraejemplo-Todo grafo es simétrico.
F, es un grafo dirigido-Un digrafo es un grafo con no más de dos aristas entre cada par de vértices.
F, deben poseer ,además, igual conexión de vértices-Dos grafos son isomorfos entre sí cuando presentan tanto mismo número de vértices como de aristas.
F, puede no tener ciclo- Un grafo es bipartito si y sólo si todo ciclo en el grafo tiene longitud par.
F, toda arista que posee debe pertenecer al grafo original-Un grafo es bipartito cuando el conjunto de aristas es particionado en tres subconjuntos.
V- El problema del "Vendedor Viajero" está asociado con los ciclos Eulerianos.
V- Un árbol de n vértices tiene exactamente n-1 aristas.
V- El orden de un grafo corresponde al número total de vértices del mismo
Conceptos y terminología
– F Un grafo bipartito completo posee un número par de vértices.
– F, es el que puede ser representado sin entrecruzamiento de aristas - Un grafo planar es aquel en que no existe entrecruzamiento de aristas.
– V Un grafo conectado con un número mínimo de aristas es un árbol.
– F Todo grafo completo es regular.
– V Un grafo bipartito con más de 5 vértices no puede ser planar.
– V Un grafo desconexo puede ser bipartito.
– F, Una clique es un subgrafo completo- No existe relación entre un grafo completo y una clique.
– V El problema del vendedor viajero consiste en encontrar un ciclo hamiltoneano de largo máximo.
– F, núm. cromático corresponde al número mínimo de colores, tal que cada vértice adyacente de un par tenga distinto color- El número cromático de un grafo corresponde al número de vértices que posee el grafo.
– F, se obtiene por la combinación de n sobre 2, donde n es el número de vértices - El número de aristas de un grafo, se obtiene de la combinación de m sobre 2, donde m es número de aristas.
– F, en el ciclo el primer vértice del conjunto es igual al último, en un circuito no - Circuito es igual a ciclo.
– F, en el ciclo el primer vértice del conjunto es igual al último, en un circuito no- Loop es un circuito de longitud 1.
Propiedades de grafos
• Para los siguientes grafos determinar
¿Es planar? Falso ¿Es 3-conexo? verdadero ¿Tiene camino hamiltoniano? Falso, es al revés tiene camino pero no tiene ciclo ya que si se parte desde el vértice de más arriba no se puede volver a este.
graph G { a -- b; b -- c; c -- d; d -- a; c -- a; b -- d; }
graph G {logout = neato a -- b -- c -- d -- a; a -- c -- l; b -- d; }
Liste 5 propiedades de los siguientes grafos
Grafo N°1: Es bipartito, Es bipartito completo, Es conexo, Tiene camino de Euler, Es un grafo no dirigido.
Grafo N°2: Es un grafo no dirigido, Es un grafo regular, Es conexo, Tiene camino de Hamilton, No tiene lazos.
Grafo N°3: Grafo ponderado, Grafo no dirigido, Tiene camino de Hamilton, Tiene camino de Euler, Es acíclico.
Grafo N°4: Grafo ponderado, Grafo conexo, Tiene camino de Euler, Es un grafo plano, Es acíclico.
• ¿Cuántas aristas tiene un grafo completo de 10 vértices?
R= Un grafo completo de 10 vértices tiene 45 aristas osea K 10:45
Propiedades de grafos
• ¿Cuántas aristas tiene un grafo completo de N vértices? R= Un grafo completo de n vértices tiene n(n-1)/2 aristas, y se denota Kn
• ¿Cuál es el número máximo de aristas que puede tener un grafo no dirigido sin ciclos?R= según lo que yo he investigado y a mi criterio como yo entiendo, Si es un ´árbol, es ac´ıclico y si tiene n vértices, tiene n − 1 aristas. ⇐c G es ac´ıclico luego es un bosque con k componentes conexas y n − k aristas. Como tiene n − 1 aristas, debe ser n − 1 = n − k de donde k = 1 y solo tiene una componente conexa, según yo el maximo es uno menos de los vertices
• Escriba las lista de adyacencia y matriz de adyacencia para los siguientes grafos
GRAFO N°1
GRAFO N°2
GRAFO N°3
Propiedades de grafos
• Liste los los ciclos posibles para el siguiente grafo
(a,15,e,16,d,20.a).
(e,30,g,12,d,16,e)
(d,20,a,15,e,35,f,15,g,19,h,21,c,28,b,22,d).
(b,22,d,12,g,19,h,21,c,28,b).
(a,20,d,16,e,35,f,15,g,19,h,21,c,28,b,12,a).
• Trace grafos con estructura de anillo, estructura de árbol y completo con 10 vértices4
Propiedades de grafos
Verifique si el siguiente grafo es bipartita. En caso se serlo, trace su resultado
imagen en el link
Dado el siguiente dibujo de líneas, ¿es posible dibujarlo con un bolígrafo, pasando una y sólo una vez por cada línea y sin levantar el bolígrafo del papel (pudiendo empezar y acabar en sitios distintos)? En caso afirmativo, dibujarlo en
el orden adecuado. En caso negativo, demostrar por qué no es posible.
imagen en el link
Propiedades de grafos
Pruebe que cada una de las siguientes gráfica tiene una trayectoria del vértice “A” al vértice “A” que pasa por cada arista justo una vez encontrando la trayectoria por inspección. Escriba y señala la trayectoria. ¿Cómo se le llama a este tipo de trayectorias?
Figura N°1 : ( a-->b, b-->e, e-->f, f-->d, d-->c, c-->a. )Camino de Euler
Figura N°2: a--b, b-->d, d-->e, e-->b, b-->c, c-->e, e-->f, f-->c, c-->a. Camino de Euler
Figura N°3: ( a-->d, d-->b, b-->e, e-->d, d--g, g-->e, e-->h, h-->g, g-->c, c-->i, i-->h, h-->f, f-->e, e-->c, c-->b, b-->a )
Camino de Euler
¿Cual es el camino más corto de s a t?
s,1-->a,2-->b,2-->c,4-->t = 9
s,1-->a,2-->e,3-->f,3-->t =9
Isomorfismo
verifica si son isomorfos
imagen en el link.
Número Cromático
• Indique el número cromático(mínimo número de colores sin que dos vértices adyacentes tengan el mismo color
imagen en el link.
Figura 1
imagen en el link.
Ejercicios
• Dos grafos son isomorfos si tienen el mismo número de vértices y los vértices de cada grafo se pueden numerar de modo que dos vértices del segundo grafo están unidos por un lado si y sólo si los dos vértices del primer grafo que tienen los mismos números están unidos por un lado.
1.- Indica qué grafos de la figura 1 son isomorfos.
imagen en el link.
• Un ciclo es cualquier camino cerrado que no pasa por ningún vértice dos veces, excepto por el vértice del comienzo, que es también el del final.
2.- En la figura 1, indica en cada apartado, cuántos ciclos distintos contienen cada uno de los grafos representados.
imagen en el link.
3.- ¿Es cierto que dos grafos deben ser isomorfos si los dos
a) ¿tienen 10 vértices de grado 9 cada uno? verdadero
b) ¿tienen 8 vértices de grado 3 cada uno?
c) son conexos, sin ciclos y tienen seis lados?
SI
4.- Prueba que no existe un grafo de 5 vértices con grados 4, 4, 4, 4 y 2
No se puede.
5.- En un grafo conexo, el grado de cuatro de los vértices es 3 y el resto de vértices tienen grado 4. Demuestra que no podemos eliminar un lado de modo que el grafo se convierta en otro con dos componentes conexas isomorfas.
• Un árbol es un grafo conexo sin ciclos.
• Un camino simple es todo camino en un grafo que no pasa por el mismo lado más de una vez.
6.- Prueba que un grafo en el que dos vértices cualesquiera están conectados por uno y sólo un camino simple es un árbol.
7.- Prueba que en cualquier árbol dos vértices cualesquiera están conectados por uno y sólo un camino simple.
8.- Prueba que en cualquier árbol con al menos un lado existe un vértice de grado 1.
9.- Si todos los vértices de un grafo tienen grado 3, prueba que el grafo tiene un ciclo
10.- Demuestra que si de un árbol se elimina un lado, el grafo resultante no es conexo.
11.- En cierto país hay 101 pueblos. Algunos están unidos por carretera, de modo que cada par de pueblos están conectados por uno y sólo un camino simple. ¿Cuántas carreteras hay?
12.- En todo árbol el número de vértices excede en uno al número de lados.
13.- Si en un grafo conexo el número de vértices excede en uno al número de lados, entonces el grafo es un árbol.
no
14.- Una red de volley tiene forma rectangular con dimensiones 50 x 600 celdillas. Cuál es el número máximo de cuerdas unidad que se pueden cortar sin que la red se divida en más de un trozo?
15.- En un país hay 30 ciudades de modo que cada una de ellas está unida a todas las demás por una carretera. ¿Cuál es el número máximo de carreteras que se pueden cortar de modo que se pueda seguir viajando de cada ciudad a cada una de las restantes?
16.- Demuestra que en un grafo conexo se puede suprimir un vértice y todos los lados que concurren en él de manera que el grafo continúa siendo conexo.
17.- Hay 100 ciudades en un país y algunas están conectadas por línea aérea. Se sabe que se puede viajar desde cualquier ciudad a cualquier otra (quizá con varias escalas). Demuestra que puedes viajar por todo el país visitando todas las ciudades realizando no más de
a)198 vuelos
b)196 vuelos.
18. Dibuje un grafo para representar seis ciudades A, B, C, D, E y F con una carretera que conecta cada par de ciudades de la siguiente lista: (A,B), (B,C), (D,E), (D,F). ¿Cuál es la valencia de cada vértice en el grafo? ¿Qué consecuencia se puede sacar de la conexión o no del grafo?
graph G { A--B; B--C; D--E; D--F; } que no es un grafo conexo
19. ¿Es posible encontrar una eulerización con 7 aristas añadidas para una red viaria rectangular de 2 manzanas por 5? ¿Es posible mejorar esa cifra?
20. ¿Es posible encontrar una eulerización con 6 aristas añadidas para una red viaria rectangular de 3 manzanas por 5? ¿Es posible mejorar esa cifra?
21. Para las siguientes gráficas verifique si contienen un circuito
Hamiltoniano, indique la secuencia seguida
22. La siguiente tabla expone la distancia en millas entre cuatro ciudades: Springfield, Ill. (S), Urbana, Ill. (U), Effingham, Ill. (E), e Indianapolis, Ind. (I).
a. Represente esta información mediante un grafo.
b. Encuentre el coste de tres circuitos Hamiltonianos distintos en el grafo.
(Anótelos empezando en U.)
c. ¿Qué circuito da el coste mínimo?
d. ¿Habría alguna diferencia en las partes b y c si el vértice de comienzo fuera I?
23. Para construir un nuevo cuarto en una casa hay que completar las siguientes tareas. Haga unas estimaciones razonables de tiempo para realizar estas tareas y represéntelas en un digrafo con requerimiento de orden. ¿Cuál es el menor tiempo en el que se pueden terminar todas estas tareas?
a. Poner los cimientos.
b. Erigir paredes.
c. Poner tejado.
d. Instalación de fontanería.
e. Instalación eléctrica.
f. Colocar baldosas.
g. Obtener permisos de construcción.
h. Instalar puerta que conecta nuevo cuarto con la casa existente.
i. Instalar lámparas en el techo.
24. Dibujar todos los arboles con raíz que tienen 5 vertices.
25. Construir un spanning tree del grafo siguiente a) usando el criterio de depth-first b) breadth-first. En ambos casos usar como raíz el vértice
26. Caracterizar aquellos grafos para los cuales los criterios depth-first y breadth-first resultan en el mismo spanning tree
27. Que tipos de grafos tienen el mismo spanning tree usando depth-first no importa cual sea el vertice de partida.
28. Al grafo siguiente aplicar a) el algoritmo de Kruskal y b) el algoritmo de Dijkstra partiendo de S.
29. En el siguiente grafo dirigido hallar el mínimo camino de S a T usando el método de Bellman. Previamente numerar los vertices tal que si uv entonces u<v.
30. En la siguiente gráfica los vertices representan ciudades y los números sobre las aristas son los costos de construir las carreteras indicadas. Encuentre el sistema de carreteras menos costoso que conecte todas las ciudades. ¿Cómo se le llama al árbol resultante?
Grado de un Vértice
Definición. Sean G un grafo y v un vértice de G. El grado de v, denotado por grad (v), es el número de aristas que salen de v. Una arista que sea un lazo, secuenta dos veces.
Gráficas planas
Definición: Una gráfica es plana si se puede trazar sobre un plano sin que sus aristas se crucen. Verifique si la gráfica es plana.
Verifique si las siguientes gráficas son planas.
Coloración. Colorea el mapa con el mínimo número de colores posibles sin juntarse dos colores
• Dibuje el grafo correspondiente al mapa de México, considerando que el país se divide en 32 regiones. ¿Cuál es el número cromático de este grafo?.
Àrboles
Ejercicios
Verifique si son o no árboles
En los árboles que a continuación se presentan responda: a) nivel de cada hoja, b) altura del árbol y c) liste todos los descendientes del vértice b en cada àrbol.
1. a) e,g-2 h,i,j,k-3
b) 3
c) d,e,h,i
2. a) d-1 f-2 j-3 k,l-4
b) 3
c) e, f, h, k
3. a) i-2 k-3 j-5
b) 53
c) i
Recorridos en árboles binarios
Liste el procesamiento de los nodos al realizar los recorridos en Pre-orden, entre-Orden y Post-Orden Recorra en PreOrden, EnOrden y PostOrden
PreOrden: 18,12,5,9,28,20,35
Inorden: 9,5,12,18,28,35,20
PostOrden 9,5,12,20,35,28,18
PreOrden : 10,2,6,3,1,7,4,6,9,11,5,8
EnOrden: 3,6,1,2,7,4,6,1,0,5,1,1,9,8
PostOrden. 3,1,6,4,6,72,5,1,1,8,9,1,0
PreOrden: P,B,H,J,E,F,G,C,D,I,K,L,M
EnOrden : H,J,F,E,G,B,P,D,C,I,L,K,M
PostOrden F,G,E,J,H,B,D,L,M,K,I,C,P
imagen en el link
PreOrden A,B,H,I,K,L,M,J,C,D,E,F,G
EnOrden I,L,K,M,H,J,B,A,O,F,E,G,C
PostOrden L,M,K,I,J,H,B,F,G,E,D,C,A
Enumerar en orden de Preorden
Ejercicio 3: Tarea 19
imagen en el link
PreOrden A,B,E,G,K,L,M,H,C,D,I,N,Q,O,R,S,T,F,J,P
EnOrden G,L,K,M,E,H,B,A,D,N,Q,I,O,S,R,T,C,F,J,P
PostOrden L,M,K,G,H,E,B,Q,N,S,T,R,O,I,D,F,J,P,C,A
imagen en el link.
PreOrden /++FE---GHI*JD++ABC
EnOrden F+E+G-H-I-J*D/A+B+C
PostOrden FE+GH-I-JD*-AB+C+/
imagen en el link.
Pre-orden L-F-5-I-H-8-9-P-Q-4-A-B-C-1-M-6-G-N-2-7-K-D-3-J
In-orden
I-5-Q-P-9-8-H-A-4-F-1-C-B-L-6-M-K-7-D-2-J-3-N-G
Post-orden
I-Q-P-9-8-A-4-H-5-1-C-B-F-6-K-D-7-J-3-2-N-G M-L
imagen en el lin
Pre-orden
37-24-7-2-32-42-40-42-120
In-orden
2-7-24-32-37-40-42-120-42
Post-orden
2-7-32-24-40-120-42-42-37
imagen en el link.
Pre-orden
(A*B-C/D+E)+(A-B-C-D*D)/(A+B+C)
Ejercicios de árboles binarios de búsqueda
• Construya el árbol de búsqueda binaria para las siguientes secuencias de datos
1) 1 , 36, 2, 3, 4, 5, 10, 9, 8, 50, 65, 34, 21, 76, 68, 12
2) 1070221, 1020057 , 1070399, 1070285, 1070542, 1070764, 1070863,
1050243, 1050614, 1050423 , 1070009
3) 1040672, 1070288, 1070457, 1040751, 0961431, 1070490, 1070031,1050250, 1070778
4) a, f, h, t, b, j, k, l, m, c, n, d, e, f, n, o, g, i, p, r
5) 153, 436, 5, 174, 229, 349, 56, 655, 60, 855, 666, 88, 374, 37, 20
6) 5, 52, 7, 45, 10, 106, 104, 384, 600, 34, 21, 78, 29
Ejercicios de árboles binarios de búsqueda
• Dibujar un árbol binario búsqueda con la secuencia de letras N, S, F, Q, D, J, X, C, U, E, L, Z, L, O, K considerando el orden de las 26 letras del alfabeto
• Escribir la secuencia de letras que resulta de recorrer el árbol anterior en preorden, enorden y postorden.
Pre-orden
N-F-D-C-E-J-L-K-L-S-Q-O-X-U-Z
In-orden
C-D-E-F-J-K-L-L-N-O-Q-S-U-X-Z
Post-orden
C-E-D-K-L-L-J-F-O-Q-U-Z-X-S-N
Cómo guardarías un árbol en un arreglo
• Esquematice la forma en que se almacenan cada uno de los siguientes árboles binarios dentro de un arreglo
Inciso A
Inciso B
Código de Huffman
• Hallar el código de Huffman en el siguiente caso
Código de Huffman : 10111000000101001111
Comentarios
Publicar un comentario