REPÚBLICA BOLOVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL POLICTECNICA
DE LA FUERZA ARMADA NACIONAL
CARRERA: INGENIERIA EN SITEMAS
ASIGNATURA: TEORIA DE GRAFOS
1ERA PRUEBA
DOCENTE: ALUMNA:
RODOLFO QUIJADA ANA GABRIELA CARDOZO
C.I.V-28310291
1.- PRUEBE SU ALGORITMO CON LOS SIGUIENTES GRAFOS
PRUEBA A
A). # Definimos el número de nodos
nodos = 11
# Creamos una matriz de adyacencia de nodos x nodos, inicializada
en 0
matriz_adyacencia = [[0 for _ in range(nodos)] for _ in
range(nodos)]
# Función para agregar una arista dirigida de nodo1 a nodo2
def agregar_arista(matriz, nodo1, nodo2):
matriz[nodo1][nodo2] = 1
# Agregamos las aristas dirigidas
aristas = [(0, 1), (0, 4), (0, 6), (1, 0), (1, 2), (1, 7), (2,
1), (2, 3), (2, 8), (3, 2), (3, 4), (3, 9), (4, 0), (4, 3), (4,
5), (5, 4), (5, 6), (5, 9), (6, 0), (6, 5), (6, 7), (6, 10), (7,
1), (7, 6), (7, 8), (8, 2), (8, 7), (8, 9), (8, 10), (9, 3), (9,
5), (9, 8), (10, 8), (10, 9)]
for nodo1, nodo2 in aristas:
agregar_arista(matriz_adyacencia, nodo1, nodo2)
# Imprimimos la matriz de adyacencia
print("Matriz de Adyacencia (Dirigida):")
for fila in matriz_adyacencia:
print(fila)
# Creamos vectores para representar los nodos y sus conexiones
nodos_vectores = [[] for _ in range(nodos)]
# Llenamos los vectores con las conexiones dirigidas
for nodo1, nodo2 in aristas:
nodos_vectores[nodo1].append(nodo2)
# Imprimimos los vectores de conexiones
print("\nVectores de Conexiones (Dirigidas):")
for i, conexiones in enumerate(nodos_vectores):
Ejecución: Vectores de Conexiones (Dirigidas):
Matriz de adyacencia Nodo 0: [1, 4, 6]
(dirigible): Nodo 1: [0, 2, 7]
[0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0] Nodo 2: [1, 3, 8]
[1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0] Nodo 3: [2, 4, 9]
[0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0] Nodo 4: [0, 3, 5]
[0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1] Nodo 5: [4, 6, 9]
[0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0] Nodo 6: [0, 5, 7, 10]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
print(f"Nodo {i}: {conexiones}")
PRUEBA B
# Definimos el número de nodos
nodos = 10
# Creamos una matriz de adyacencia de nodos x nodos, inicializada
en 0
matriz_adyacencia = [[0 for _ in range(nodos)] for _ in
range(nodos)]
# Función para agregar una arista dirigida de nodo1 a nodo2
def agregar_arista(matriz, nodo1, nodo2):
matriz[nodo1][nodo2] = 1
# Agregamos las aristas dirigidas
aristas = [(0, 1), (0, 2), (0, 2), (0, 3), (0 ,5), (1, 0), (1,
3), (1, 4), (2, 0), (2, 0), (2, 4), (2, 7), (3, 0), (3, 1), (3,
5), (3, 6), (4, 1), (4, 6), (4, 6), (5, 0), (5, 2), (5, 3), (5,
6), (5, 7), (5, 8), (6,3), (6, 4), (6, 4), (6, 5), (6, 8), (6,
9), (7, 2), (7, 5), (8, 5), (8, 6), (8, 9), (9, 6), (9, 8)]
for nodo1, nodo2 in aristas:
agregar_arista(matriz_adyacencia, nodo1, nodo2)
# Imprimimos la matriz de adyacencia
print("Matriz de Adyacencia (Dirigida):")
for fila in matriz_adyacencia:
print(fila)
# Creamos vectores para representar los nodos y sus conexiones
nodos_vectores = [[] for _ in range(nodos)]
# Llenamos los vectores con las conexiones dirigidas
for nodo1, nodo2 in aristas:
nodos_vectores[nodo1].append(nodo2)
# Imprimimos los vectores de conexiones
print("\nVectores de Conexiones (Dirigidas):")
for i, conexiones in enumerate(nodos_vectores):
print(f"Nodo {i}: {conexiones}")
Vectores de Conexiones
Ejecución:
(Dirigidas):
Matriz de Adyacencia
Nodo 0: [1, 2, 2, 3, 5]
(Dirigida):
Nodo 1: [0, 3, 4]
[0, 1, 1, 1, 0, 1, 0, 0, 0, 0]
Nodo 2: [0, 0, 4, 7]
[1, 0, 0, 1, 1, 0, 0, 0, 0, 0]
Nodo 3: [0, 1, 5, 6]
[1, 0, 0, 0, 1, 0, 0, 1, 0, 0]
Nodo 4: [1, 6, 6]
[1, 1, 0, 0, 0, 1, 1, 0, 0, 0]
Nodo 5: [0, 2, 3, 6, 7, 8]
[0, 1, 0, 0, 0, 0, 1, 0, 0, 0]
Nodo 6: [3, 4, 4, 5, 8, 9]
[1, 0, 1, 1, 0, 0, 1, 1, 1, 0]
PRUEBA G1
# Definimos el número de nodos
nodos = 8
# Creamos una matriz de adyacencia de nodos x nodos, inicializada
en 0
matriz_adyacencia = [[0 for _ in range(nodos)] for _ in
range(nodos)]
# Función para agregar una arista dirigida de nodo1 a nodo2
def agregar_arista(matriz, nodo1, nodo2):
matriz[nodo1][nodo2] = 1
# Agregamos las aristas dirigidas
aristas = [(0, 1), (0, 2), (0, 6), (1, 0), (1, 2), (1, 4), (1,
7), (2, 0), (2, 1), (2, 4), (2, 3), (3, 2), (3, 5), (3, 6), (4,
1), (4, 2), (4, 5), (5, 3), (5, 4), (5, 6), (5, 7), (6, 0), (6,
3), (6,5), (6, 7), (7, 1), (7, 5), (7, 6)]
for nodo1, nodo2 in aristas:
agregar_arista(matriz_adyacencia, nodo1, nodo2)
# Imprimimos la matriz de adyacencia
print("Matriz de Adyacencia (Dirigida):")
for fila in matriz_adyacencia:
print(fila)
# Creamos vectores para representar los nodos y sus conexiones
nodos_vectores = [[] for _ in range(nodos)]
# Llenamos los vectores con las conexiones dirigidas
for nodo1, nodo2 in aristas:
nodos_vectores[nodo1].append(nodo2)
# Imprimimos los vectores de conexiones
print("\nVectores de Conexiones (Dirigidas):")
for i, conexiones in enumerate(nodos_vectores):
print(f"Nodo {i}: {conexiones}")
Ejecución:
Vectores de Conexiones
Matriz de Adyacencia (Dirigida):
(Dirigidas):
[0, 1, 1, 0, 0, 0, 1, 0]
Nodo 0: [1, 2, 6]
[1, 0, 1, 0, 1, 0, 0, 1]
Nodo 1: [0, 2, 4, 7]
[1, 1, 0, 1, 1, 0, 0, 0]
Nodo 2: [0, 1, 4, 3]
[0, 0, 1, 0, 0, 1, 1, 0]
Nodo 3: [2, 5, 6]
[0, 1, 1, 0, 0, 1, 0, 0]
Nodo 4: [1, 2, 5]
[0, 0, 0, 1, 1, 0, 1, 1]
Nodo 5: [3, 4, 6, 7]
[1, 0, 0, 1, 0, 1, 0, 1]
[0, 1, 0, 0, 0, 1, 1, 0]
Prueba G2
# Definimos el número de nodos
nodos = 8
# Creamos una matriz de adyacencia de nodos x nodos, inicializada
en 0
matriz_adyacencia = [[0 for _ in range(nodos)] for _ in
range(nodos)]
# Función para agregar una arista dirigida de nodo1 a nodo2
def agregar_arista(matriz, nodo1, nodo2):
matriz[nodo1][nodo2] = 1
# Agregamos las aristas dirigidas
aristas = [(0, 1), (0, 2), (0, 6), (1, 0), (1, 2), (1, 4), (1,
7), (2, 0), (2, 1), (2, 3), (2, 4), (3, 2), (3, 5), (3, 6), (4,
1), (4, 2), (4, 5), (4, 7), (5, 3), (5, 4), (5, 7), (6, 0), (6,
3), (6,7), (7, 1), (7, 4), (7, 5), (7, 6)]
for nodo1, nodo2 in aristas:
agregar_arista(matriz_adyacencia, nodo1, nodo2)
# Imprimimos la matriz de adyacencia
print("Matriz de Adyacencia (Dirigida):")
for fila in matriz_adyacencia:
print(fila)
# Creamos vectores para representar los nodos y sus conexiones
nodos_vectores = [[] for _ in range(nodos)]
# Llenamos los vectores con las conexiones dirigidas
for nodo1, nodo2 in aristas:
nodos_vectores[nodo1].append(nodo2)
# Imprimimos los vectores de conexiones
print("\nVectores de Conexiones (Dirigidas):")
for i, conexiones in enumerate(nodos_vectores):
print(f"Nodo {i}: {conexiones}")
Ejecución: Vectores de Conexiones (Dirigidas):
Matriz de Adyacencia (Dirigida): Nodo 0: [1, 2, 6]
[0, 1, 1, 0, 0, 0, 1, 0] Nodo 1: [0, 2, 4, 7]
[1, 0, 1, 0, 1, 0, 0, 1] Nodo 2: [0, 1, 3, 4]
[1, 1, 0, 1, 1, 0, 0, 0] Nodo 3: [2, 5, 6]
[0, 0, 1, 0, 0, 1, 1, 0] Nodo 4: [1, 2, 5, 7]
[0, 1, 1, 0, 0, 1, 0, 1] Nodo 5: [3, 4, 7]
[0, 0, 0, 1, 1, 0, 0, 1] Nodo 6: [0, 3, 7]
En una sala hay 30 equipos informáticos con 73 pares de conexiones entre
ellos.
1). Demuestra que hay al menos un equipo que está conectado a lo sumo a
otros 4 equipos.
Para resolver esto, usaremos el principio del palomar (principio de Dirichlet). Si
distribuimos “n” objetos en “m” compartimentos y “n > m”, al menos un
compartimento contendrá más de un objeto.
En este caso, los 30 equipos informáticos son los objetos y las conexiones entre
ellos son los compartimentos.
Si asumimos que cada equipo está conectado a al menos 5 equipos (es decir, el
grado de cada vértice es al menos 5), entonces el número total mínimo de
conexiones sería:
(30 * 5) / (2) = 75
Esto se debe a que cada conexión se cuenta dos veces, una vez para cada equipo
en el par. Pero tenemos solo 73 conexiones, lo que significa que la suposición de
que cada equipo está conectado a al menos 5 equipos es incorrecta.
Por lo tanto, debe haber al menos un equipo que esté conectado a lo sumo a
otros 4 equipos.
2. Supongamos ahora que hay un equipo C que está conectado a algún otro y
que es el único que cumple que el número de conexiones a otros equipos es a
lo sumo 4. Demuestra que los demás equipos están conectados exactamente a
5 equipos cada uno. Calcula el número exacto de conexiones entre C y otros
equipos.
Primero, sabemos que hay un equipo C con un grado máximo de 4.
El número total de grados (conexiones) en el grafo es 2 * 73 = 14. Esto se debe a
que cada conexión contribuye al grado de dos equipos.
Si C tiene un grado de 4, los demás 29 equipos deben tener un total combinado de
146 - 4 = 142 grados.
Si C es el único equipo con un grado distinto de 5, entonces los demás 29 equipos
deben tener grados sumando 142 :
29 * 5 = 145
Pero, esto no cuadra, ya que el total debería ser 142. Por lo tanto, C tiene un grado
inferior a 4, permitiendo que los otros grados sumen correctamente a 142, y
demostrando que los demás equipos están conectados exactamente a 5 equipos
cada uno.
Para calcular el número exacto de conexiones entre C y otros equipos, dado que C
tiene un grado de 4:
Número de conexiones = 4
