EXAMEN 1
Universidad Surcolombiana.
Curso: Teoría de grafos.
Docente: Dr (c). Alexander Paredes Martínez.
1. Tres señores y tres criados deben cruzar el río en una barca que solo permite
que viajen dos personas. Solo hay un problema, los caballeros tienen motivos
para sospechar que los sirvientes han conspirado entre ellos para robar a los
señores y matarles. Por lo tanto, los caballeros son conscientes de que en
ningún momento puede haber más criados que señores en alguna de las
orillas, puesto que les matarían. ¿Cómo podrán cruzar el río?
Aborde el problema anterior desde teoría de grafos y modele todas las posibles
soluciones del problema. Además, puede considerar el número de criados y de
señores en la orilla de inicio como (c , s).
Si c es el número de criados que hay en la primera orilla, y s el de
señores, entonces un par (c, s) describe la situación en cada momento
en la primera orilla, y por lo tanto, también en la segunda. La situación
inicial sería (3,3) y la final (0,0). En total hay 16 posibles estados, pares
de números, pero algunos no son posibles por las condiciones del
problema, como (0,1), (0,2), (1,2), (2,1), (3,1) y (3,2), en estos casos los
criados superan a los señores en alguna de las dos orillas. El resto de
pares, que sí son posibles, los representamos en el plano cartesiano, y
van a ser los vértices de nuestro grafo.
Ahora unimos esos vértices con aristas dirigidas, de forma que una
arista dirigida que une dos posiciones, quiere decir que al cruzar la barca
de la primera orilla a la segunda se pasa de la primera situación a la
segunda, y por lo tanto, la dirección opuesta a la marcada representará
a la barca pasando de la segunda orilla a la primera.
Entonces, la solución
Entonces, la solución consiste en encontrar un camino, en el grafo
dirigido, que empiece en el (3,3) y termine en el (0,0), alternando aristas
en el sentido positivo (el marcado en el grafo) y en sentido negativo (el
contrario al marcado), representando las idas y venidas de la barca. Una
solución se muestra en la imagen (las aristas con línea discontinua son
aquellas en las que se viaja de la segunda orilla a la primera, es decir, el
sentido inverso al marcado en el grafo dirigido).
2. Supongamos que en un grafo bipartito, todos los vértices excepto posiblemente
uno de ellos tienen el mismo grado d , y el vértice restante tiene un grado
desconocido x. Demuestre que x debe ser múltiplo de d (0 , d , 2 d , 3 d , …)
Answer
Step 1/8
1. In a bipartite graph, the vertices can be divided into two disjoint sets, say U and V, such that
every edge connects a vertex in U to a vertex in V.
Step 2/8
2. Let's assume that the size of set U is m and the size of set V is n. So, there are m vertices in
U and n vertices in V.
Step 3/8
3. Since all vertices except one have the same degree d, there are m-1 vertices in U with
degree d and n-1 vertices in V with degree d.
Step 4/8
4. Let's assume that the vertex with unknown degree x is in set U. Then, the sum of degrees of
all vertices in U is (m-1)d + x.
Step 5/8
5. The sum of degrees of all vertices in a graph is equal to twice the number of edges. So, the
sum of degrees of all vertices in U and V is 2E, where E is the number of edges in the graph.
Traducción.
Paso 1/8
1. En un grafo bipartito, los vértices se pueden dividir en dos conjuntos
disjuntos, digamos U y V, de modo que cada borde conecte un vértice en
U con un vértice en V.
Paso 2/8
2. Supongamos que el tamaño del conjunto U es m y el tamaño del
conjunto V es n. Entonces, hay m vértices en U y n vértices en V.
Paso 3/8
3. Dado que todos los vértices, excepto uno, tienen el mismo grado d, hay
m-1 vértices en U con grado d y n-1 vértices en V con grado d.
Paso 4/8
4. Supongamos que el vértice con grado desconocido x está en el
conjunto U. Entonces, la suma de los grados de todos los vértices en U
es (m-1)d + x.
Paso 5/8
5. La suma de grados de todos los vértices en un gráfico es igual al doble
del número de aristas. Entonces, la suma de los grados de todos los
vértices en U y V es 2E, donde E es el número de aristas en el gráfico.
