kockagráf
Kiejtés
- IPA: [ ˈkot͡skɒɡraːf]
Főnév
kockagráf
Kockagráf definíció
A **kockagráf** egy speciális gráf, amely egy -dimenziós **hiperkocka** szomszédsági struktúráját reprezentálja. A gráf:
- **Csúcsai**: Az -dimenziós hiperkocka csúcsai, amelyeket a vektorok reprezentálnak.
- **Élei**: Két csúcs között akkor van él, ha a két vektor között pontosan **egy bit különbség** van (Hamming-távolságuk 1).
Tulajdonságai
1. **Rendezett gráf**: -dimenzió esetén minden csúcs fokszáma pontosan .
2. **Köröket tartalmaz**: A gráf zárt köröket is tartalmaz, de nem tartalmaz párhuzamos éleket (pl. 2-ciklusokat).
3. **Irányítatlan**: A kockagráf irányítatlan gráf.
4. **Bipartit gráf**: A csúcsok két diszjunkt halmazra oszthatók, ahol minden él a két halmaz között húzódik.
5. **Összefüggő gráf**: Az -dimenziós kockagráf mindig összefüggő.
Példák
1-dimenziós kockagráf ( )
- Csúcsok:
- Élek:
2-dimenziós kockagráf ( )
- Csúcsok:
- Élek:
- Vizualizáció**: Egy négyzet.
3-dimenziós kockagráf ( )
- Csúcsok:
- Élek: Két csúcs között akkor van él, ha Hamming-távolságuk 1.
- Vizualizáció**: Egy kocka.
Kockagráf generálása Pythonban
Hamming-távolság számítás
def hamming_distance(a, b):
return sum(x != y for x, y in zip(a, b))
Kockagráf generálása
import itertools
import networkx as nx
import matplotlib.pyplot as plt
def generate_hypercube_graph(n):
# Csúcsok: minden lehetséges bináris vektor az n dimenzióban
nodes = [''.join(seq) for seq in itertools.product('01', repeat=n)]
# Gráf inicializálása
G = nx.Graph()
G.add_nodes_from(nodes)
# Élek hozzáadása (Hamming-távolság = 1)
for u in nodes:
for v in nodes:
if hamming_distance(u, v) == 1:
G.add_edge(u, v)
return G
# Példa: 3-dimenziós kockagráf
Q3 = generate_hypercube_graph(3)
# Vizualizáció
pos = nx.spring_layout(Q3, seed=42)
nx.draw(Q3, pos, with_labels=True, node_color='lightblue', node_size=500)
plt.show()
Incidenciamátrix kockagráfhoz
A kockagráf incidenciamátrixát a csúcsok (bináris vektorok) és élek alapján készítjük.
import numpy as np
def adjacency_matrix_hypercube(n):
nodes = [''.join(seq) for seq in itertools.product('01', repeat=n)]
size = len(nodes)
matrix = np.zeros((size, size), dtype=int)
for i, u in enumerate(nodes):
for j, v in enumerate(nodes):
if hamming_distance(u, v) == 1:
matrix[i][j] = 1
return matrix, nodes
# Példa: 3-dimenziós kockagráf
matrix, nodes = adjacency_matrix_hypercube(3)
print("Csúcsok:", nodes)
print("Adjacency matrix:\n", matrix)
Kockagráfok tulajdonságainak vizsgálata
Fokszám ellenőrzése
def verify_degrees(graph, n):
for node in graph.nodes:
if graph.degree(node) != n:
return False
return True
# Fokszám ellenőrzés a Q3 gráfra
is_valid = verify_degrees(Q3, 3)
print("Fokszám helyes:", is_valid)
Összefüggőség ellenőrzése
is_connected = nx.is_connected(Q3)
print("Összefüggő:", is_connected)
Alkalmazások
1. **Adattárolás és kommunikáció**:
A kockagráfokat gyakran használják az adatszervezésben, mivel a csúcsok közötti minimális bitváltoztatással történő elérés Hamming-távolságon alapul.
2. **Párhuzamos számítás**:
Számítógépes hálózatok, ahol a csomópontok közötti minimális kommunikáció szükséges.
3. **Hibajavító kódok**:
A Hamming-távolságra épülő hibajavítási algoritmusok a kockagráf struktúráját használják.
Összegzés
A kockagráfok matematikailag egyszerű, de erőteljes struktúrák, amelyek számos alkalmazásban hasznosak. Pythonban könnyen generálhatók és elemezhetők a `networkx` könyvtár segítségével, akár magas dimenziókban is.