Ejercicios De Grafos Desarroyados

Universidad Ricardo Palma

Esc. Profesional de Ingeniería Informática

Ejercicios Resueltos Sobre Grafos
VERDADERO O FALSO, COMENTE LAS FALSAS. 1. Un grafo bipartito completo puede tener una clique. 2. Todo grafo es simétrico. V F

3. Un digrafo es un grafo con no más de dos aristas entre cada par de vértices. F, es un grafo dirigido. 4. Dos grafos son isomorfos entre sí cuando presentantanto mismo número de vértices como de aristas. F, deben poseer ,además, igual conexión de vértices. 5. Un p-grafo es un grafo regular de grado p. F, donde al menos un par de vértices se encuentra conectado por tres aristas. 6. Todo grafo hamiltoneano es biconexo, luego todo grafo que no sea biconexo no puede ser hamiltoneano. V 7. Un grafo es bipartito si y sólo si todo ciclo en el grafo tienelongitud par. F, puede no tener ciclo. 8. Un subgrafo generado puede tener aristas distintas del grafo original. F, toda arista que poseea debe pertenecer al grafo original. 9. Un subgrafo inducido puede tener aristas distintas del grafo original. F, toda arista que poseea debe pertenecer al grafo original. 10. El orden de un grafo corresponde al número total de vértices del mismo. 11. Circuito esigual a ciclo. F, en el ciclo el primer vértice del conjunto es igual al último, en un circuito no. 12. Loop es un circuito de longitud 1. 13. El complemento de un grafo totalmente disconexo es siempre una clique. 14. Un grafo bipartito completo posee un número par de vértices. 15. Un grafo planar es aquel en que no existe entrecruzamiento de aristas. F, es el que puede ser representado sinentrecruzamiento de aristas. 16. Un grafo conectado con un número mínimo de aristas es un árbol. V V V V

F, ej. K23

17. El grado de un vértice en un digrafo es la cantidad de arcos que salen de él menos los que llegan. F, los que salen menos los que llegan. Mg. Guillermo Antonio Mas Azahuanche 1

Universidad Ricardo Palma 18. Todo grafo completo es regular.

Esc. Profesional de IngenieríaInformática F, ej. K23 V

19. Un grafo bipartito con más de 5 vértices no puede ser planar. 20. El complemento de un grafo conexo no puede tener ciclo hamiltoneano.

F, si puede tener C.H. 21. Un grafo conexo no puede tener conjunto independiente. F. Todo grafo conexo tiene conjunto independiente de vértices. 22. Un grafo disconexo pude ser bipartito. 23. No existe relación entre un grafo completoy una clique. F, Una clique es un subgrafo completo. 24. El problema del vendedor viajero consiste en encontrar un ciclo hamiltoneano de largo máximo. V 25. El número cromático de un grafo corresponde al número de vértices que posee el grafo. 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. 26. El número de aristas de ungrafo, se obtiene de la combinación de m sobre 2, donde m es número de aristas. F, se obtiene por la combinación de n sobre 2, donde n es el número de vértices. 27. Un grafo es bipartito cuando el conjunto de aristas es particionado en tres subconjuntos. F, es bipartito cuando el conjunto de vértices es particionado en dos subconjuntos. 28. El problema del "Vendedor Viajero" está asociado con losciclos Eulerianos. F, con Hamiltoneanos. 29. Kn es planar para 1  n  5 . 30. Un árbol de n vértices tiene exactamente n-1 aristas. 31. Un "corte de vértices" es un conjunto minimal. 32. La representación planar satisface la relación n+f=m+2, donde: n es número de vértices, m es número de aristas y f es número de fases. F, K5 no es planar. V V V V

33. Un grafo G(N;A) tal que |N|=5 y |A|=10 nopuede tener número cromático igual a 4. V

Mg. Guillermo Antonio Mas Azahuanche

2

Universidad Ricardo Palma 34. Los siguientes grafos son isomorfos.

Esc. Profesional de Ingeniería Informática V

35. Sea S un conjunto y S’ S . Se dice que S’ es maximal para una propiedad P si: el conjunto S’ satisface P y además no existe ningún conjunto S’’ S que también satisface P tal que |S’’| >...