Ejercicios · AyG PUJ · Introduccion a grafos¶
Los primeros se hacen en papel y no toman más de veinte minutos: sirven para fijar el vocabulario antes de programar. Los dos últimos van al juez en línea.
Sobre el grafo de la clase¶
El grafo \(G_1\) tiene siete vértices, numerados de 0 a 6, y las aristas \(\{0,1\}\), \(\{0,4\}\), \(\{0,5\}\), \(\{1,2\}\), \(\{1,3\}\), \(\{1,4\}\), \(\{2,5\}\).
- Escriba \(N(1)\) y \(N(6)\), y la secuencia de grado del grafo.
- Verifique el apretón de manos contando las aristas por los dos lados.
- Escriba \(G_1\) en las tres representaciones y confirme que las tres dan los mismos vecinos para el vértice 1.
- Agregue la arista \(\{3,6\}\) y diga qué cambia en cada una de las tres.
Sobre las familias¶
- ¿Existe un grafo simple con secuencia de grado \(3,3,3,3,2\)? ¿Y con \(1,2,3,4,4\)? ¿Y con \(1,2,3,4,5\)? Use el apretón de manos antes de intentar dibujarlos.
- ¿Cuántos vértices tiene un grafo regular de grado 4 con 10 aristas?
- Dibuje el complemento de \(C_5\) y diga qué familia resulta.
- ¿Cuántas aristas tiene el complemento de \(K_{3,3}\)?
Sobre las representaciones¶
- Un grafo tiene \(V = 10\,000\) y \(E = 30\,000\). Calcule cuánta memoria ocupa en cada una de las tres representaciones, contando un entero por posición.
- Escriba una función que reciba una matriz de adyacencia y devuelva la lista de adyacencia equivalente. ¿Cuánto cuesta?
- Escriba la función inversa. ¿Cuánto cuesta ahora, y por qué no es lo mismo?
- Un algoritmo pregunta \(10^6\) veces si existe la arista \((u,v)\) sobre un grafo de 500 vértices. ¿Cuál representación conviene y por qué?
UVa 10928 — My Dear Neighbours¶
Enunciado y envío: https://vjudge.net/problem/UVA-10928
Cada línea de la entrada trae los vecinos de un lugar, y no dice cuántos son: hay que partir la línea y contar cuántos quedaron. El enunciado avisa que si \(P_1\) tiene a \(P_2\) como vecino no se sigue lo contrario, así que el grafo es dirigido y lo que se pide es el grado de salida. Se imprimen todos los lugares que empatan en el mínimo, ordenados y separados por un espacio. Los casos van separados por una línea en blanco.
UVa 11550 — Demanding Dilemma¶
Enunciado y envío: https://vjudge.net/problem/UVA-11550
Dan una matriz de \(n \times m\) y preguntan si puede ser la matriz de incidencia de un grafo simple no dirigido. Las dos condiciones salen de la definición: cada columna representa una arista, así que debe tener exactamente dos unos, y como el grafo es simple no puede haber dos aristas entre el mismo par de vértices, es decir, dos columnas iguales.