Capítulo I. Grafos, nociones básicas

1. Construir un grafo de orden 5 cuyos vértices tengan grados 1, 2, 2, 3, 4. ¿Cuál es el tamaño del grafo?

2. A una fiesta asisten 20 invitados. Cada uno de ellos conoce a un número diferente de invitados. ¿Es esto posible? Probar que todo grafo sin bucles de orden n>2 tiene al menos dos vértices con el mismo grado.

3. En un mapa de carreteras de una región aparecen 25 tramos de carretera. Sabiendo que los cruces de carretera se producen siempre en una población y que de cada lugar parten al menos cuatro caminos, ¿cuántos lugares aparecen en el mapa?

4. Si G es un grafo simple con 52 aristas, ¿cuál es el menor número de vértices que puede tener G?

5. Dibujar los grafos simples no isomorfos de orden 4.

6. Disponemos de 6 ordenadores y 9 cables de conexión. Queremos que cada ordenador se conecte con otros 3 ordenadores. ¿Existe alguna forma de conectarlos? ¿Es única?

7. Determinar cuáles de los siguientes grafos son bipartidos:

8. ¿Cuántas aristas tiene un grafo simple si sus vértices tienen los siguientes grados 4,3,3,2,2? Dibuja tal grafo.

9. Obtenga las matrices de adyacencia e incidencia para los siguientes grafos:

10. Representa la matriz de adyacencia de cada uno de los siguientes grafos:
a) K4
b) K1,4
c) K2,3
d) C4
e) W4
f) Q3

11.   Determinar cuáles de los siguientes pares de grafos son isomorfos:

12.   Halla los vértices-corte y los bloques de los siguientes grafos:

13.  Dar un ejemplo de un grafo conexo G que contenga un vértice v tal que G-{v} tenga cinco componentes.

DESCARGAR ESTE ARCHIVO EN PDF