← Materiały bloku: Kwantowe wyżarzanie kombinatorycznych problemów optymalizacyjnych  ·  podgląd notatnika wprowadzenie_do_teorii_grafow.ipynb  ·  pobierz plik .ipynb

Łagodne wprowadzenie do teorii grafów

Teoria grafów bada struktury złożone z wierzchołków i krawędzi. Można jej używać do opisywania wielu sytuacji z życia codziennego, na przykład:

• sieci dróg między miastami,
• połączeń między komputerami,
• relacji znajomości między osobami.

W tym notatniku poznamy kilka podstawowych pojęć.

1. Graf nieskierowany

Graf nieskierowany to para złożona z:

• zbioru wierzchołków,
• zbioru krawędzi łączących niektóre pary wierzchołków.

W grafie nieskierowanym połączenie nie ma kierunku. Jeżeli wierzchołek $A$ jest połączony z $B$, to jednocześnie $B$ jest połączony z $A$.

Możemy to zapisać symbolicznie jako:

$$G = (V, E)$$

gdzie:

• $V$ oznacza zbiór wierzchołków,
• $E$ oznacza zbiór krawędzi.

2. Wierzchołki i krawędzie

Wierzchołki

Wierzchołki to podstawowe obiekty grafu. Można o nich myśleć jak o punktach.

Przykład: w sieci kolejowej wierzchołkami mogą być miasta.

Krawędzie

Krawędzie to połączenia między wierzchołkami.

Przykład: jeśli dwa miasta są połączone linią kolejową, to między odpowiadającymi im wierzchołkami rysujemy krawędź.

Jeśli mamy wierzchołki $A$, $B$, $C$ oraz krawędzie $AB$ i $BC$, to oznacza to, że:

• $A$ jest połączony z $B$,
• $B$ jest połączony z $C$,
• ale $A$ nie jest połączony z $C$.

3. Przykład prostego grafu nieskierowanego

Rozważmy graf o wierzchołkach:

$$V = \{A, B, C, D\}$$

oraz krawędziach:

$$E = \{\{A,B\}, \{A,C\}, \{C,D\}, \{A,D\}\}$$

To znaczy, że:

• $A$ łączy się z $B$,
• $A$ łączy się z $C$,
• $C$ łączy się z $D$.

Nie ma tu na przykład krawędzi między $B$ i $D$.

import matplotlib.pyplot as plt
import networkx as nx

# Mały graf nieskierowany
G = nx.Graph()
G.add_edges_from([
    ("A", "B"),
    ("A", "C"),
    ("C", "D"),
    ("A", "D"),
])

pos = {
    "A": (0, 1),
    "B": (1, 1.8),
    "C": (2, 1),
    "D": (1, 0.2),
}

plt.figure(figsize=(8, 6))
nx.draw(
    G,
    pos,
    with_labels=True,
    node_size=1800,
    node_color="lightblue",
    font_size=14,
    width=2,
)

# Strzałka i podpis do wierzchołka
plt.annotate(
    "To jest wierzchołek",
    xy=pos["B"],
    xytext=(1.8, 2.4),
    arrowprops=dict(arrowstyle="->", lw=2, color="blue"),
    fontsize=12,
)

# Strzałka i podpis do krawędzi
x1, y1 = pos["A"]
x2, y2 = pos["B"]
srodek_krawedzi = ((x1 + x2) / 2, (y1 + y2) / 2)
plt.annotate(
    "To jest krawędź",
    xy=srodek_krawedzi,
    xytext=(-0.2, 2.2),
    arrowprops=dict(arrowstyle="->", lw=2, color="blue"),
    fontsize=12,
)


plt.axis("off")
plt.tight_layout()
plt.show()

C:\Users\walle\AppData\Local\Temp\ipykernel_12612\2805171619.py:54: UserWarning: This figure includes Axes that are not compatible with tight_layout, so results might be incorrect.
  plt.tight_layout()

4. Graf pełny

Graf pełny to taki graf, w którym każda para różnych wierzchołków jest połączona krawędzią.

Innymi słowy: każdy wierzchołek jest połączony z każdym innym.

Graf pełny o $n$ wierzchołkach oznaczamy zwykle przez:

$$K_n$$

Przykład

Graf pełny $K_4$ ma 4 wierzchołki i wszystkie możliwe połączenia między nimi.

Liczba krawędzi w grafie pełnym $K_n$ wynosi:

$$\frac{n(n-1)}{2}$$

Na przykład dla $n = 4$ otrzymujemy:

$$\frac{4\cdot 3}{2} = 6$$

czyli graf $K_4$ ma 6 krawędzi.

import matplotlib.pyplot as plt
import networkx as nx

# Graf pełny K4: każdy wierzchołek jest połączony z każdym innym
n = 4
G = nx.complete_graph(n)
labels = {i: chr(65 + i) for i in range(n)}
pos = nx.circular_layout(G)

plt.figure(figsize=(6, 6))
nx.draw(
    G,
    pos,
    labels=labels,
    with_labels=True,
    node_size=1800,
    node_color="lightgreen",
    font_size=14,
    width=2,
)

plt.title("Graf pełny K4")
plt.axis("off")
plt.tight_layout()
plt.show()

C:\Users\walle\AppData\Local\Temp\ipykernel_12612\4121204527.py:24: UserWarning: This figure includes Axes that are not compatible with tight_layout, so results might be incorrect.
  plt.tight_layout()

5. Graf dwudzielny

Graf dwudzielny to taki graf, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory, na przykład $U$ i $W$, tak aby:

• każda krawędź łączyła wierzchołek z $U$ z wierzchołkiem z $W$,
• nie było krawędzi między dwoma wierzchołkami należącymi do tego samego zbioru.

Można to sobie wyobrazić jako dwa „rzędy” punktów, gdzie połączenia idą tylko między rzędami.

Przykład

Niech:

$$U = \{u_1, u_2, u_3\}, \qquad W = \{w_1, w_2, w_3, w_4\}$$

Jeśli krawędzie łączą niektóre $u_i$ z niektórymi $w_j$, to taki graf może być grafem dwudzielnym.

Przykładowe zastosowanie:

• jeden zbiór oznacza uczniów,
• drugi zbiór oznacza koła zainteresowań,
• krawędź oznacza, że dany uczeń należy do danego koła.

import matplotlib.pyplot as plt
import networkx as nx

# Graf dwudzielny: wierzchołki dzielą się na dwa zbiory
lewa_czesc = ["U1", "U2", "U3"]
prawa_czesc = ["W1", "W2", "W3", "W4"]

G = nx.Graph()
G.add_nodes_from(lewa_czesc, bipartite=0)
G.add_nodes_from(prawa_czesc, bipartite=1)
G.add_edges_from([
    ("U1", "W1"),
    ("U1", "W3"),
    ("U2", "W2"),
    ("U2", "W4"),
    ("U3", "W1"),
    ("U3", "W4"),
])

pos = {}
for i, node in enumerate(lewa_czesc):
    pos[node] = (0, len(lewa_czesc) - i)
for i, node in enumerate(prawa_czesc):
    pos[node] = (2, len(prawa_czesc) - i)

colors = ["lightsalmon" if node in lewa_czesc else "lightblue" for node in G.nodes()]

plt.figure(figsize=(7, 6))
nx.draw(
    G,
    pos,
    with_labels=True,
    node_size=1800,
    node_color=colors,
    font_size=12,
    width=2,
)

plt.text(-0.2, 3.5, "Zbiór U", fontsize=12)
plt.text(2.05, 4.5, "Zbiór W", fontsize=12)
plt.title("Przykładowy graf dwudzielny")
plt.axis("off")
plt.tight_layout()
plt.show()

C:\Users\walle\AppData\Local\Temp\ipykernel_12612\3414875583.py:43: UserWarning: This figure includes Axes that are not compatible with tight_layout, so results might be incorrect.
  plt.tight_layout()

6. Graf pełny dwudzielny

Szczególnym przypadkiem grafu dwudzielnego jest graf pełny dwudzielny.

Oznaczamy go przez:

$$K_{m,n}$$

Oznacza to, że:

• pierwszy zbiór ma $m$ wierzchołków,
• drugi zbiór ma $n$ wierzchołków,
• każdy wierzchołek z pierwszego zbioru jest połączony z każdym wierzchołkiem z drugiego zbioru.

Na przykład $K_{3,4}$ ma:

• 3 wierzchołki w pierwszej części,
• 4 wierzchołki w drugiej części,
• razem $3 \cdot 4 = 12$ krawędzi.

7. Cykl Eulera i cykl Hamiltona

Cykl Eulera to taka droga w grafie, która przechodzi przez każdą krawędź dokładnie jeden raz i wraca do punktu startowego. Najważniejsze jest tu więc odwiedzanie krawędzi.

Przykład: wyobraź sobie rysunek, który da się narysować jednym pociągnięciem ołówka i wrócić do miejsca startu, nie rysując żadnej linii drugi raz.

Cykl Hamiltona to cykl, który odwiedza każdy wierzchołek dokładnie jeden raz i wraca do wierzchołka początkowego. Tutaj najważniejsze są więc wierzchołki, a nie krawędzie.

Czyli w skrócie:

• cykl Eulera — każda krawędź raz,
• cykl Hamiltona — każdy wierzchołek raz.

To ważna różnica: w cyklu Eulera patrzymy na przejście po liniach grafu, a w cyklu Hamiltona na odwiedzenie wszystkich punktów grafu.

8. Podsumowanie

Najważniejsze pojęcia:

• graf nieskierowany - graf, w którym krawędzie nie mają kierunku,
• wierzchołki - punkty grafu,
• krawędzie - połączenia między wierzchołkami,
• graf pełny - graf, w którym każda para różnych wierzchołków jest połączona,
• graf dwudzielny - graf, którego wierzchołki można podzielić na dwa zbiory, a krawędzie biegną tylko między tymi zbiorami.
• cykl Eulera - droga w grafie, która przechodzi przez każdą krawędź dokładnie jeden raz i wraca do punktu startowego.
• cykl Hamiltona - groga w grafie, która odwiedza każdy wierzchołek dokładnie jeden raz i wraca do wierzchołka początkowego.

Literatura

• Diestel, R. (2000). Graph Theory

• Wilson, R. J. (2007). Wprowadzenie do teorii grafów.