Przeczytaj

W tej sekcji znajdziesz przykłady implementacji reprezentacji grafów nieskierowanych bez wag w języku Python. Reprezentacje te zostały przedstawione w e‑materiale teoretycznymPpkZaFlK1e‑materiale teoretycznym, są to macierz sąsiedztwa, lista sąsiedztwa, macierz incydencji.

Grafy nieskierowane

Macierz sąsiedztwa

Dany jest następujący graf spójny nieskierowany bez wag:

R1OA3UoJEctUA

Ilustracja przedstawia pięciokąt wypukły. Jego wierzchołki są oznaczone kolejno cyframi 4, 0, 1, 2, 5. Wierzchołek 4 oraz 1 jest połączony przekątną, tak samo jak wierzchołek 2 i 0. Z wierzchołka 4 oraz 2 wychodzą proste, które spotykają się w punkcie oznaczonym 3, który znajduje się wewnątrz figury. Wszystkie wierzchołki i punkty są oznaczone niebieskimi kółkami. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Jego macierz sąsiedztwamacierz sąsiedztwamacierz sąsiedztwa wygląda tak:

R12LrCWhJbLTN

Ilustracja przedstawia tabelkę sześć na sześć kratek. Jej kolumny i rzędy są oznaczone cyframi od 0 do 5. W pierwszym rzędzie wpisano 0, 1, 1, 0, 1, 0, w drugim rzędzie 1, 0, 1, 0, 1, 0, w trzecim rzędzie, 1, 1, 0, 1, 0, 1, w czwartym rzędzie 0, 0, 1, 0, 1, 0, w piątym rzędzie 1, 1, 0, 1, 0, 1, w szóstym rzędzie 0, 0, 1, 0, 1, 0. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Najprostszym sposobem przechowywania macierzy sąsiedztwa jest użycie tablicy dwuwymiarowej, która w języku Python odpowiada zagnieżdżonym listom.

macierzSasiedztwa = [
	[0, 1, 1, 0, 1, 0],
	[1, 0, 1, 0, 1, 0],
	[1, 1, 0, 1, 0, 1],
	[0, 0, 1, 0, 1, 0],
	[1, 1, 0, 1, 0, 1],
	[0, 0, 1, 0, 1, 0]
]

Może się zdarzyć, że program rozpocznie pracę od grafu niezawierającego żadnych krawędzi, którego reprezentacja to po prostu macierz wypełniona samymi zerami. W takim przypadku możemy wygenerować listę składaną z użyciem funkcji range().

Na potrzeby naszej implementacji macierz sąsiedztwa będzie dwuwymiarową tablicą statyczną o V wierszach i V kolumnach (V to liczba wierzchołków grafu).

macierzSasiedztwa = [[0] * n for _ in range(V)]

Po zastosowaniu przedstawionego kodu:

V = 6
macierzSasiedztwa = [[0] * V for _ in range(V)]
for wiersz in macierzSasiedztwa: print(wiersz)

otrzymamy następujący wynik:

[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

Łączenie wierzchołków grafu nieskierowanego nowymi krawędziami zrealizujemy, odwołując się do odpowiednich wyrazów listy. Aby to zrobić, należy wyrazom macierzSasiedztwa[i][j] i macierzSasiedztwa[j][i] przypisać wartość 1.

Zmienne i oraz j to indeksy łączonych wierzchołków.

macierzSasiedztwa[i][j] = 1
macierzSasiedztwa[j][i] = 1
for wiersz in macierzSasiedztwa: print(wiersz)

Napiszmy program, który pozwoli nam obserwować, jak zmieniają się macierze sąsiedztwa. Najpierw wyświetli pierwotną macierz, a po dodaniu nowej krawędzi - nową macierz.

Linia 1. macierzSasiedztwa znak równości otwórz nawias kwadratowy. Linia 2. otwórz nawias kwadratowy 0 przecinek 1 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 3. otwórz nawias kwadratowy 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 4. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 5. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 6. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 7. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 8. zamknij nawias kwadratowy. Linia 9. print otwórz nawias okrągły cudzysłów Pierwotna postac dwukropek cudzysłów zamknij nawias okrągły. Linia 10. for wiersz in macierzSasiedztwa dwukropek print otwórz nawias okrągły wiersz zamknij nawias okrągły. Linia 11. macierzSasiedztwa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy otwórz nawias kwadratowy 5 zamknij nawias kwadratowy znak równości 1. Linia 12. macierzSasiedztwa otwórz nawias kwadratowy 5 zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 1. Linia 13. print otwórz nawias okrągły cudzysłów Polacz wierzcholki 0 i 5 dwukropek cudzysłów zamknij nawias okrągły. Linia 14. for wiersz in macierzSasiedztwa dwukropek print otwórz nawias okrągły wiersz zamknij nawias okrągły. Linia 15. macierzSasiedztwa otwórz nawias kwadratowy 2 zamknij nawias kwadratowy otwórz nawias kwadratowy 4 zamknij nawias kwadratowy znak równości 1. Linia 16. macierzSasiedztwa otwórz nawias kwadratowy 4 zamknij nawias kwadratowy otwórz nawias kwadratowy 2 zamknij nawias kwadratowy znak równości 1. Linia 17. print otwórz nawias okrągły cudzysłów Polacz wierzcholki 2 i 4 dwukropek cudzysłów zamknij nawias okrągły. Linia 18. for wiersz in macierzSasiedztwa dwukropek print otwórz nawias okrągły wiersz zamknij nawias okrągły.

macierzSasiedztwa = [
	[0, 1, 1, 0, 1, 0],
	[1, 0, 1, 0, 1, 0],
	[1, 1, 0, 1, 0, 1],
	[0, 0, 1, 0, 1, 0],
	[1, 1, 0, 1, 0, 1],
	[0, 0, 1, 0, 1, 0]
]
print("Pierwotna postac: ")
for wiersz in macierzSasiedztwa: print(wiersz)
macierzSasiedztwa[0][5] = 1
macierzSasiedztwa[5][0] = 1
print("Polacz wierzcholki 0 i 5: ")
for wiersz in macierzSasiedztwa: print(wiersz)
macierzSasiedztwa[2][4] = 1
macierzSasiedztwa[4][2] = 1
print("Polacz wierzcholki 2 i 4: ")
for wiersz in macierzSasiedztwa: print(wiersz)

W konsoli program wypisze następujące wyrazy macierzy:

Linia 1. Pierwotna postac dwukropek. Linia 2. otwórz nawias kwadratowy 0 przecinek 1 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 3. otwórz nawias kwadratowy 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 4. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy. Linia 5. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 6. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy. Linia 7. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 8. Polacz wierzcholki 0 i 5 dwukropek. Linia 9. otwórz nawias kwadratowy 0 przecinek 1 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias kwadratowy. Linia 10. otwórz nawias kwadratowy 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 11. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy. Linia 12. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 13. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy. Linia 14. otwórz nawias kwadratowy 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 15. Polacz wierzcholki 2 i 4 dwukropek. Linia 16. otwórz nawias kwadratowy 0 przecinek 1 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias kwadratowy. Linia 17. otwórz nawias kwadratowy 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 18. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 1 przecinek 1 przecinek 1 zamknij nawias kwadratowy. Linia 19. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 20. otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy. Linia 21. otwórz nawias kwadratowy 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy.

Pierwotna postac: 
[0, 1, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 0]
[1, 1, 0, 1, 0, 1]
[0, 0, 1, 0, 1, 0]
[1, 1, 0, 1, 0, 1]
[0, 0, 1, 0, 1, 0]
Polacz wierzcholki 0 i 5: 
[0, 1, 1, 0, 1, 1]
[1, 0, 1, 0, 1, 0]
[1, 1, 0, 1, 0, 1]
[0, 0, 1, 0, 1, 0]
[1, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 0]
Polacz wierzcholki 2 i 4: 
[0, 1, 1, 0, 1, 1]
[1, 0, 1, 0, 1, 0]
[1, 1, 0, 1, 1, 1]
[0, 0, 1, 0, 1, 0]
[1, 1, 1, 1, 0, 1]
[1, 0, 1, 0, 1, 0]

Przyjrzyjmy się graficznemu przedstawieniu wyniku.

Tak wygląda pierwotna postać macierzy:

RMZb5uA3j5aOO

Ilustracja przedstawia tabelkę sześć na sześć kratek. Jej kolumny i rzędy są ponumerowane od 0 do 5. W pierwszym rzędzie znajdują się następujące cyfry: 0, 1, 1, 0, 1, 0, w drugim rzędzie 1, 0, 1, 0, 1, 0, w trzecim rzędzie 1, 1, 0, 1, 0, 1, w czwartym rzędzie 0, 0, 1, 0, 1, 0 w piątym rzędzie 1, 1, 0, 1, 0, 1, w szóstym rzędzie 0, 0, 1, 0, 1, 0. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Chcemy połączyć wierzchołki 0 oraz 5:

RVITL4mqUTBis

Po połączeniu wierzchołków macierz wygląda następująco:

Rue4hjdslZXQk

W przypadku łączenia innych wierzchołków sytuacja wygląda analogicznie.

Lista sąsiedztwa

Dany jest następujący graf spójny nieskierowany bez wag:

R1OA3UoJEctUA

Jego lista sąsiedztwa wygląda następująco:

Rri8wpXPrqHIU

Ilustracja przedstawia cyfry znajdujące się w ramkach. Każdy rząd oznaczony jest cyfrą od 0 do 5, która znajduje się w niebieskiej ramce, pozostałe ramki w rzędach są czarne. W pierwszym rzędzie oznaczonym cyfrą 0 w czarnych ramkach znajduje się cyfra 1, strzałka, cyfra 2, strzałka, cyfra 4. W drugim rzędzie oznaczonym cyfrą 1 znajdują się cyfry 0, 2, 4, w trzecim oznaczonym cyfrą 2 cyfry 0, 1, 3, 5, w czwartym rzędzie oznaczonym cyfrą 3 są cyfry 2, 4, w piątym rzędzie oznaczonym cyfrą 4 cyfry 0, 1, 3, 5, a w szóstym rzędzie oznaczonym cyfrą 5 cyfry 2, 4. Wszystkie liczby w rzędach są połączone strzałkami skierowanymi w prawo. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Słownik w języku Python to nieuporządkowany zbiór wartości, służący do przechowywania danych. W przeciwieństwie do innych struktur danych (których poszczególne elementy są pojedynczymi wartościami) słownik przechowuje pary klucz: wartość.

listaSasiedztwa = {
	0: [1, 2, 4],
	1: [0, 2, 4],
	2: [0, 1, 3, 5],
	3: [2, 4],
	4: [0, 1, 3, 5],
	5: [2, 4]
}

Słownik może stanowić reprezentację grafu w postaci listy sąsiedztwalista sąsiedztwalisty sąsiedztwa, o ile za klucz przyjmiemy nazwę wierzchołka, a lista jego sąsiadów będzie wartością dla tego klucza. Sam wierzchołek możemy uczynić obiektem dowolnego typu.

listaSasiedztwa = {
	'A': ['B', 'C'],
	'B': ['A', 'C', 'D'],
	'C': ['A', 'B', 'D', 'E'],
	'D': ['B', 'C'],
	'E': ['C', 'F'],
	'F': ['E']
}

Ciekawostka

Należy pamiętać, że w przypadku słowników metoda iter() odwołuje się do kluczy. Oznacza to, że jeśli umieścimy słownik wewnątrz pętli for, metoda iter() będzie zwracać kolejne referencje do kluczy.

listaSasiedztwa = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}
for klucz in listaSasiedztwa: print(klucz)

Wynik działania programu:

A
B
C

listaSasiedztwa = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}
for klucz in listaSasiedztwa: print(listaSasiedztwa[klucz])

Wynik działania programu:

['B']
['A', 'C']
['B']

Dodawanie nowych wierzchołków do listy sąsiadów zrealizujemy dzięki metodzie append(), która dołącza nowy element do końca listy.

listaSasiedztwa['A'].append('C')
for klucz in listaSasiedztwa: print(listaSasiedztwa[klucz])

Wynik działania programu:

['B', 'C']
['A', 'C']
['B']

Wróćmy do przykładu. Dany jest pewien graf, którego reprezentacją jest lista sąsiedztwa (przechowywana za pomocą struktury danych, którą nazywamy słownikiem). By połączyć ze sobą wierzchołki, wykorzystamy opisaną wyżej metodę append(). Połączymy wierzchołki 0 i 5 oraz 2 i 4. Mamy do czynienia z grafem nieskierowanym, zatem do listy sąsiadów wierzchołka 0 dodamy wierzchołek 5, a do listy sąsiadów wierzchołka 5 dodamy wierzchołek 0. Analogicznie postąpimy z drugą parą wierzchołków.

Kod programu:

Linia 1. listaSasiedztwa znak równości otwórz nawias klamrowy. Linia 2. 0 dwukropek otwórz nawias kwadratowy 1 przecinek 2 przecinek 4 zamknij nawias kwadratowy przecinek. Linia 3. 1 dwukropek otwórz nawias kwadratowy 0 przecinek 2 przecinek 4 zamknij nawias kwadratowy przecinek. Linia 4. 2 dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 3 przecinek 5 zamknij nawias kwadratowy przecinek. Linia 5. 3 dwukropek otwórz nawias kwadratowy 2 przecinek 4 zamknij nawias kwadratowy przecinek. Linia 6. 4 dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 3 przecinek 5 zamknij nawias kwadratowy przecinek. Linia 7. 5 dwukropek otwórz nawias kwadratowy 2 przecinek 4 zamknij nawias kwadratowy. Linia 8. zamknij nawias klamrowy. Linia 10. print otwórz nawias okrągły cudzysłów Pierwotna postac dwukropek cudzysłów zamknij nawias okrągły. Linia 11. for klucz in listaSasiedztwa dwukropek print otwórz nawias okrągły klucz przecinek cudzysłów dwukropek cudzysłów przecinek listaSasiedztwa otwórz nawias kwadratowy klucz zamknij nawias kwadratowy zamknij nawias okrągły. Linia 12. listaSasiedztwa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy kropka append otwórz nawias okrągły 5 zamknij nawias okrągły. Linia 13. listaSasiedztwa otwórz nawias kwadratowy 5 zamknij nawias kwadratowy kropka append otwórz nawias okrągły 0 zamknij nawias okrągły. Linia 14. print otwórz nawias okrągły cudzysłów Polacz wierzcholki 0 i 5 dwukropek cudzysłów zamknij nawias okrągły. Linia 15. for klucz in listaSasiedztwa dwukropek print otwórz nawias okrągły klucz przecinek cudzysłów dwukropek cudzysłów przecinek listaSasiedztwa otwórz nawias kwadratowy klucz zamknij nawias kwadratowy zamknij nawias okrągły. Linia 16. listaSasiedztwa otwórz nawias kwadratowy 2 zamknij nawias kwadratowy kropka append otwórz nawias okrągły 4 zamknij nawias okrągły. Linia 17. listaSasiedztwa otwórz nawias kwadratowy 4 zamknij nawias kwadratowy kropka append otwórz nawias okrągły 2 zamknij nawias okrągły. Linia 18. print otwórz nawias okrągły cudzysłów Polacz wierzcholki 2 i 4 dwukropek cudzysłów zamknij nawias okrągły. Linia 20. for klucz in listaSasiedztwa dwukropek print otwórz nawias okrągły klucz przecinek cudzysłów dwukropek cudzysłów przecinek listaSasiedztwa otwórz nawias kwadratowy klucz zamknij nawias kwadratowy zamknij nawias okrągły.

listaSasiedztwa = {
	0: [1, 2, 4],
	1: [0, 2, 4],
	2: [0, 1, 3, 5],
	3: [2, 4],
	4: [0, 1, 3, 5],
	5: [2, 4]
}

print("Pierwotna postac: ")
for klucz in listaSasiedztwa: print(klucz,":",listaSasiedztwa[klucz])
listaSasiedztwa[0].append(5)
listaSasiedztwa[5].append(0)
print("Polacz wierzcholki 0 i 5: ")
for klucz in listaSasiedztwa: print(klucz,":",listaSasiedztwa[klucz])
listaSasiedztwa[2].append(4)
listaSasiedztwa[4].append(2)
print("Polacz wierzcholki 2 i 4: ")

for klucz in listaSasiedztwa: print(klucz,":",listaSasiedztwa[klucz])

Wyjście programu:

Linia 1. Pierwotna postac dwukropek. Linia 2. 0 dwukropek otwórz nawias kwadratowy 1 przecinek 2 przecinek 4 zamknij nawias kwadratowy. Linia 3. 1 dwukropek otwórz nawias kwadratowy 0 przecinek 2 przecinek 4 zamknij nawias kwadratowy. Linia 4. 2 dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 3 przecinek 5 zamknij nawias kwadratowy. Linia 5. 3 dwukropek otwórz nawias kwadratowy 2 przecinek 4 zamknij nawias kwadratowy. Linia 6. 4 dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 3 przecinek 5 zamknij nawias kwadratowy. Linia 7. 5 dwukropek otwórz nawias kwadratowy 2 przecinek 4 zamknij nawias kwadratowy. Linia 8. Polacz wierzcholki 0 i 5 dwukropek. Linia 9. 0 dwukropek otwórz nawias kwadratowy 1 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 10. 1 dwukropek otwórz nawias kwadratowy 0 przecinek 2 przecinek 4 zamknij nawias kwadratowy. Linia 11. 2 dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 3 przecinek 5 zamknij nawias kwadratowy. Linia 12. 3 dwukropek otwórz nawias kwadratowy 2 przecinek 4 zamknij nawias kwadratowy. Linia 13. 4 dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 3 przecinek 5 zamknij nawias kwadratowy. Linia 14. 5 dwukropek otwórz nawias kwadratowy 2 przecinek 4 przecinek 0 zamknij nawias kwadratowy. Linia 15. Polacz wierzcholki 2 i 4 dwukropek. Linia 16. 0 dwukropek otwórz nawias kwadratowy 1 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 17. 1 dwukropek otwórz nawias kwadratowy 0 przecinek 2 przecinek 4 zamknij nawias kwadratowy. Linia 18. 2 dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 3 przecinek 5 przecinek 4 zamknij nawias kwadratowy. Linia 19. 3 dwukropek otwórz nawias kwadratowy 2 przecinek 4 zamknij nawias kwadratowy. Linia 20. 4 dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 3 przecinek 5 przecinek 2 zamknij nawias kwadratowy. Linia 21. 5 dwukropek otwórz nawias kwadratowy 2 przecinek 4 przecinek 0 zamknij nawias kwadratowy.

Pierwotna postac: 
0 : [1, 2, 4]
1 : [0, 2, 4]
2 : [0, 1, 3, 5]
3 : [2, 4]
4 : [0, 1, 3, 5]
5 : [2, 4]
Polacz wierzcholki 0 i 5: 
0 : [1, 2, 4, 5]
1 : [0, 2, 4]
2 : [0, 1, 3, 5]
3 : [2, 4]
4 : [0, 1, 3, 5]
5 : [2, 4, 0]
Polacz wierzcholki 2 i 4: 
0 : [1, 2, 4, 5]
1 : [0, 2, 4]
2 : [0, 1, 3, 5, 4]
3 : [2, 4]
4 : [0, 1, 3, 5, 2]
5 : [2, 4, 0]

Przyjrzyj się temu, jak w pierwszym przypadku zmieniły się wiersze nr 9 oraz 14.

W drugim przypadku zwróć uwagę na wiersze nr 18 oraz 20.

Macierz incydencji

Dany jest następujący graf spójny nieskierowany bez wag:

R1SLuEuzVC4ye

Jego macierz incydencjimacierz incydencjimacierz incydencji wygląda tak:

R1QaZxcGv9w33

Ilustracja przedstawia tabelkę z dziewięcioma kolumnami i sześcioma rzędami. Kolumny są ponumerowane kolejno e0, e1, aż do e8, a rzędy od 0 do 5. W pierwszym rzędzie znajdują się następujące cyfry: 1, 1, 1, 0, 0, 0, 0, 0, 0, w drugim rzędzie 1, 0, 0, 1, 1, 0, 0, 0, 0, w trzecim rzędzie 0, 1, 0, 1, 0, 1, 1, 0, 0, w czwartym rzędzie 0, 0, 0, 0, 0, 1, 0, 1, 0, w piątym rzędzie 0, 0, 1, 0, 1, 0, 0, 1, 1, w szóstym rzędzie 0, 0, 0, 0, 0, 0, 1, 0, 1. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Podobnie jak macierz sąsiedztwa, macierz incydencji będzie po prostu listą V list, z których każda odpowiada innemu wierzchołkowi.

macierzIncydencji = [
	[1, 1, 1, 0, 0, 0, 0, 0, 0],
	[1, 0, 0, 1, 1, 0, 0, 0, 0],
	[0, 1, 0, 1, 0, 1, 1, 0, 0],
	[0, 0, 0, 0, 0, 1, 0, 1, 0],
	[0, 0, 1, 0, 1, 0, 0, 1, 1],
	[0, 0, 0, 0, 0, 0, 1, 0, 1]
]

Bardzo często trzeba rozpocząć program od pustej macierzy incydencji, do której w dalszych etapach pracy dodaje się nowe wyrazy. Aby zdefiniować taka pustą macierz w języku Python, zainicjalizujemy listę pustych list.

macierzIncydencji = [[] for _ in range(V)]

Łączenie wierzchołków nowymi krawędziami można zrealizować na wiele sposobów. Jeden z nich polega na dodaniu do każdej z list wewnątrz listy macierzIncydencji elementu zerowego, z wyjątkiem list na pozycjach i oraz j, odpowiadających wierzchołkom, które chcemy połączyć.

def polaczWierzcholek(macierzIncydencji, i, j):
	for wiersz in macierzIncydencji:
		wiersz.append(0)

	macierzIncydencji[i][-1] = 1
	macierzIncydencji[j][-1] = 1

Macierz incydencji w takim przypadku zmienia swój rozmiar w zależności od rzeczywistej liczby krawędzi.

Kod programu:

Linia 1. def polaczWierzcholki otwórz nawias okrągły macierzIncydencji przecinek i przecinek j zamknij nawias okrągły dwukropek. Linia 2. for wiersz in macierzIncydencji dwukropek. Linia 3. wiersz kropka append otwórz nawias okrągły 0 zamknij nawias okrągły. Linia 5. macierzIncydencji otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy minus 1 zamknij nawias kwadratowy znak równości 1. Linia 6. macierzIncydencji otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias kwadratowy minus 1 zamknij nawias kwadratowy znak równości 1. Linia 8. macierzIncydencji znak równości otwórz nawias kwadratowy. Linia 9. otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 10. otwórz nawias kwadratowy 1 przecinek 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 11. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 12. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 13. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 14. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy. Linia 15. zamknij nawias kwadratowy. Linia 16. print otwórz nawias okrągły cudzysłów Pierwotna postac dwukropek cudzysłów zamknij nawias okrągły. Linia 17. for wiersz in macierzIncydencji dwukropek print otwórz nawias okrągły wiersz zamknij nawias okrągły. Linia 19. print otwórz nawias okrągły cudzysłów Polacz wierzcholki 0 i 5 dwukropek cudzysłów zamknij nawias okrągły. Linia 20. polaczWierzcholki otwórz nawias okrągły macierzIncydencji przecinek 0 przecinek 5 zamknij nawias okrągły. Linia 21. for wiersz in macierzIncydencji dwukropek print otwórz nawias okrągły wiersz zamknij nawias okrągły. Linia 23. print otwórz nawias okrągły cudzysłów Polacz wierzcholki 2 i 4 dwukropek cudzysłów zamknij nawias okrągły. Linia 24. polaczWierzcholki otwórz nawias okrągły macierzIncydencji przecinek 2 przecinek 4 zamknij nawias okrągły. Linia 25. for wiersz in macierzIncydencji dwukropek print otwórz nawias okrągły wiersz zamknij nawias okrągły.

def polaczWierzcholki(macierzIncydencji, i, j):
	for wiersz in macierzIncydencji:
		wiersz.append(0)

	macierzIncydencji[i][-1] = 1
	macierzIncydencji[j][-1] = 1

macierzIncydencji = [
	[1, 1, 1, 0, 0, 0, 0, 0, 0],
	[1, 0, 0, 1, 1, 0, 0, 0, 0],
	[0, 1, 0, 1, 0, 1, 1, 0, 0],
	[0, 0, 0, 0, 0, 1, 0, 1, 0],
	[0, 0, 1, 0, 1, 0, 0, 1, 1],
	[0, 0, 0, 0, 0, 0, 1, 0, 1]
]
print("Pierwotna postac: ")
for wiersz in macierzIncydencji: print(wiersz)

print("Polacz wierzcholki 0 i 5: ")
polaczWierzcholki(macierzIncydencji, 0, 5)
for wiersz in macierzIncydencji: print(wiersz)

print("Polacz wierzcholki 2 i 4: ")
polaczWierzcholki(macierzIncydencji, 2, 4)
for wiersz in macierzIncydencji: print(wiersz)

Wyjście programu:

Linia 1. Pierwotna postac dwukropek. Linia 2. otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 3. otwórz nawias kwadratowy 1 przecinek 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 4. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 5. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 6. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 1 zamknij nawias kwadratowy. Linia 7. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy. Linia 8. Polacz wierzcholki 0 i 5 dwukropek. Linia 9. otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 zamknij nawias kwadratowy. Linia 10. otwórz nawias kwadratowy 1 przecinek 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 11. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 12. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 13. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 14. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias kwadratowy. Linia 15. Polacz wierzcholki 2 i 4 dwukropek. Linia 16. otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 17. otwórz nawias kwadratowy 1 przecinek 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 18. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 1 zamknij nawias kwadratowy. Linia 19. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 20. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy. Linia 21. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 zamknij nawias kwadratowy.

Pierwotna postac: 
[1, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 1, 1, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 1, 0]
[0, 0, 1, 0, 1, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 0, 1]
Polacz wierzcholki 0 i 5: 
[1, 1, 1, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 1, 1, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 1, 0, 0]
[0, 0, 1, 0, 1, 0, 0, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 1, 0, 1, 1]
Polacz wierzcholki 2 i 4: 
[1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0]
[1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1]
[0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0]

Zwróć uwagę, że po prawej stronie pojawiły się nowe kolumny – odpowiadają one nowo powstałym krawędziom grafu.

Słownik

graf

struktura składająca się z niepustego zbioru wierzchołków oraz rodziny krawędzi; dla grafu G zbiór wierzchołków oznaczamy jako V(G) (ang. verticies – wierzchołki), a zbiór krawędzi – E(G) (ang. edges – krawędzie); liczbę elementów zbioru V(G) oznaczamy literą n; liczbę elementów zbioru E(G) – m (oprac. na podst.: R. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 2007)

graf spójny

graf, którego nie można przedstawić w postaci sumy dwóch grafów (oprac. na podst.: R. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 2007)

graf ważony

graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa

izomorfizm

własność grafów mówiąca o tym, że liczba krawędzi łączących dane dwa wierzchołki jednego grafu jest równa liczbie krawędzi łączących odpowiadające im wierzchołki drugiego grafu (oprac. na podst.: R. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 2007)

krawędź

nieuporządkowana para (niekoniecznie różnych) elementów zbioru wierzchołków (oprac. na podst.: R. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 2007)

lista sąsiedztwa

zestaw $| V |$ uporządkowanych list, gdzie lista o indeksie $i$ jest listą wszystkich sąsiadów wierzchołka $i$

macierz

dwuwymiarowa tablica elementów (zwykle liczbowych), licząca $n$ wierszy i $m$ kolumn

macierz incydencji

macierz zerojedynkowa $M$ rozmiaru $| V | \times | E |$ , dla której każda krawędź grafu musi mieć unikatowy indeks; wyraz $m_{i,e}$ jest równy $1$ , o ile krawędź o indeksie $e$ jest incydentna do wierzchołka $i$

macierz sąsiedztwa

macierz zerojedynkowa $A$ rozmiaru $| V | \times | V |$ , w której wyraz $a_{i,j}$ jest równy $1$ , jeśli wierzchołki $i$ oraz $j$ są sąsiednie, a $0$ w przeciwnym przypadku; macierz sąsiedztwa jest symetryczna dla grafów nieskierowanych

pętla zasięgu (zakresowa)

pętla for pozwalająca iterować przez zdefiniowany zakres

stopień wierzchołka

liczba krawędzi incydentnych z danym wierzchołkiem (oprac. na podst.: R. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 2007)

wierzchołek

pojedynczy punkt w przestrzeni; od niego wychodzą i w nim łączą się krawędzie

Wprowadzenie

Prezentacja multimedialna

Grafy nieskierowane

Macierz sąsiedztwa

Lista sąsiedztwa

Macierz incydencji

Słownik