REPÚBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL DE LA FUERZA ARMADA NACIONAL
BOLIVARIANA
NÚCLEO: CARACAS-CHUAO
CARRERA: INGENIERÍA EN SISTEMAS
SECCIÓN: 05S-2610-D1
Grafos – Evaluación I
Profesor: Bachiller:
Rodolfo Quijada Carlos García
30.906.200
Código Fuente (Python)
import networkx as nx
import matplotlib.pyplot as plt
def generar_grafo_aleatorio(n):
"""Genera un grafo aleatorio no dirigido con aproximadamente n nodos y aristas.
Args:
n: Número de nodos (y aproximadamente de aristas).
Returns:
Un objeto NetworkX Graph.
"""
G = nx.gnm_random_graph(n, n)
return G
def dibujar_grafo(G):
"""Dibuja un grafo utilizando matplotlib.
Args:
G: Un objeto NetworkX Graph.
"""
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True)
plt.show()
Grafo A
import networkx as nx
import matplotlib.pyplot as plt
# Definimos las aristas del grafo
aristas = [
('a', 'b'), ('a', 'g'),
('b', 'c'),
('c', 'h'),
('h', 'g'),
('g', 'k'),
('k', 'j'),
('j', 'd'),
('d', 'e'),
('e', 'f'),
('f', 'k')
# Creamos el grafo
G = nx.Graph()
G.add_edges_from(aristas)
# Dibujamos el grafo
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True)
plt.show()
Grafo B
import networkx as nx
import matplotlib.pyplot as plt
# Definimos las aristas del nuevo grafo
aristas = [
('a', 'b'), ('a', 'c'), ('a', 'd'),
('b', 'd'), ('b', 'e'),
('c', 'f'), ('c', 'h'),
('d', 'f'), ('d', 'g'), ('d', 'e'),
('e', 'i'),
('f', 'g'),
('g', 'i'),
('h', 'f')
# Creamos el grafo
G = nx.Graph()
G.add_edges_from(aristas)
# Dibujamos el grafo
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True)
plt.show()
Grafo G = (V1. E1)
import networkx as nx
import matplotlib.pyplot as plt
# Definimos las aristas del nuevo grafo
aristas = [
('a', 'b'), ('a', 'c'), ('a', 'd'),
('b', 'c'), ('b', 'e'), ('b', 'h'),
('c', 'd'), ('c', 'e'),
('d', 'f'), ('d', 'g'),
('e', 'f'), ('e', 'h'),
('f', 'g'), ('f', 'h'),
('g', 'h')
# Creamos el grafo
G = nx.Graph()
G.add_edges_from(aristas)
# Dibujamos el grafo
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True)
plt.show()
Grafo G = (V2, E2)
import networkx as nx
import matplotlib.pyplot as plt
# Definimos las aristas del nuevo grafo
aristas = [
('a', 'b'), ('a', 'c'), ('a', 'd'),
('b', 'c'), ('b', 'e'), ('b', 'h'),
('c', 'd'), ('c', 'e'),
('d', 'f'), ('d', 'g'),
('e', 'f'), ('e', 'h'),
('f', 'g'), ('f', 'h'),
('g', 'h')
# Creamos el grafo
G = nx.Graph()
G.add_edges_from(aristas)
# Dibujamos el grafo
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True)
plt.show()
1. La matriz de adyacencia A de G.
La matriz de adyacencia A es una matriz cuadrada donde el elemento A [i, j] es 1 si hay una arista
entre los vértices i y j, y 0 en caso contrario.
A = [0 1 1 1 1 1]
[1 0 1 1 0 0]
[1 1 0 1 0 0]
[1 1 1 0 1 1]
[1 0 0 1 0 1]
[1 0 0 1 1 0]
2. El grado de los vértices a partir de A.
El grado de un vértice es el número de aristas que le son inherentes. Podemos calcular los grados
de la matriz de adyacencia sumando los elementos de cada fila (o columna).
Grado de v1 = 5
Grado de v2 = 4
Grado de v3 = 4
Grado de v4 = 5
Grado de v5 = 3
Grado de v6 = 3
3. ¿Tiene G alguna hoja?
No, G no tiene hojas. Una hoja es un vértice con grado 1, y todos los vértices en G tienen grados
mayores que 1.
4. ¿Tiene G alguna arista múltiple?
No, G no tiene múltiples aristas. Una arista múltiple es una arista que conecta el mismo par de
vértices más de una vez. Todas las aristas de G conectan distintos pares de vértices.
Dibuja un sub grafo de G simple de orden 3.
Un sub grafo simple de orden 3 es un grafo con 3 vértices y aristas que los conectan.
He aquí un ejemplo:
v1 --- v2 --- v3
Dibuja un sub grafo de G no simple de orden 4.
Un sub grafo no simple de orden 4 puede tener múltiples aristas o auto bucles.
Este es un ejemplo con un borde múltiple:
v1 --- v2 --- v3
| |
v4 --- v4
1. Los vértices adyacentes a v3.
Los vértices adyacentes a v3 son v1, v2 y v4.
2. Los vértices cuya distancia mínima (menor número de aristas) a v3 es 2.
Los vértices a una distancia de 2 de v3 son v5 y v6.
3. Los vértices no adyacentes a v3.
Los vértices no adyacentes a v3 son v5 y v6.
En una sala hay 30 equipos con 73 pares de conexiones entre ellos.
A._ Demuestra que hay al menos un equipo que está conectado a lo sumo a otros 4 equipos.
B._ 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.
C._ 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
A._ Para demostrar que en una sala con 30 equipos y 73 pares de conexiones entre ellos hay al
menos un equipo que está conectado a lo sumo a otros 4 equipos, utilizaremos el Teorema de
Dirichlet (también conocido como el principio de la casilla).
Planteamiento del problema
Datos iniciales:
Número de equipos n=30n=30
Número de conexiones m=73m=73
Grado de los vértices:
Cada conexión entre dos equipos se puede representar como un arista en un
grafo, donde cada equipo es un vértice.
El grado de un vértice (equipo) es el número de conexiones que tiene.
Cálculo del grado promedio:
El número total de conexiones (aristas) en un grafo se relaciona con el grado
promedio de los vértices mediante la fórmula:
Grado promedio = 2m/n
Sustituyendo los valores:
Grado promedio = 2×73/30 = 30146 ≈ 4.87
Dado que el grado promedio es aproximadamente 4.87, esto implica que, en promedio, cada
equipo está conectado a más de 4 equipos. Sin embargo, no todos los equipos pueden tener un
grado mayor a 4, ya que esto resultaría en un total de conexiones mayor al disponible.
B._ Planteamiento del problema
Datos iniciales:
Número de equipos n = 30
Número de conexiones m=73
Suposición: Existe un equipo C que está conectado a un máximo de 4 otros
equipos.
Grado del equipo C:
El grado del equipo C como grado(C) ≤4grado (C) ≤4.
Grados de los otros equipos:
Dado que C es el único equipo con un grado a lo sumo 4, los otros 29 equipos deben tener grados
mayores o iguales a 5.
Cálculo del total de conexiones
Grado total
Si consideramos que los otros 29 equipos tienen al menos un grado de 5:
Total de conexiones =
Dado que el grado del equipo CC es a lo sumo 4, podemos expresar la suma de los grados de los
otros equipos como:
Sustituyendo:
Entonces, considerando que grado(C) ≤4grado (C) ≤4:
Comparación con el número total de conexiones
Ahora, calculamos el total de conexiones basado en los grados:
Esto implica que el número total de conexiones sería al menos 74.5, lo cual no es posible ya que
tenemos solo 73 conexiones disponibles.
C._ Planteamiento del problema
Datos iniciales:
Número de equipos n=30
Número total de conexiones m=73
Se ha demostrado previamente que al menos un equipo está conectado a lo sumo
a 4 equipos (en este caso, el equipo C).
Suposiciones:
Supongamos que el equipo C tiene un grado kC tal que kC≤4.
Los otros 29 equipos deben tener un grado ki≥5.
Grado total de los equipos
Si denotamos el grado del equipo C como kC, y los grados de los otros 29 equipos como k1, k2,…,
k29, podemos expresar la suma total de los grados de todos los equipos como:
Dado que sabemos que:
kC≤4
kj = 5 para j = 1,2,...,29 (suponiendo que queremos demostrar que todos tienen
exactamente 5 conexiones)
Suma de grados
Si asumimos que cada uno de los otros 29 equipos está conectado exactamente a 5 otros equipos,
entonces:
Por lo tanto, la suma total de los grados es:
Total de conexiones
Sabemos que el total de conexiones se relaciona con la suma de los grados mediante la fórmula:
Sustituyendo:
Multiplicando ambos lados por 2:
Resolviendo para kC:
Esto implica que el equipo C está conectado solo a un equipo.
