Sprawdź się

Pokaż ćwiczenia:

RQK2jK1N4AxSi1

Ćwiczenie 1

RKaxxqCU867J71

Ćwiczenie 2

Uzupełnij tabelę będącą macierzą sąsiedztwa grafu, którego macierz incydencji ma następującą postać: A równa się, w macierzy zapisano: Linia 1: zero, zero, jeden, jeden, zero. Linia 2: zero, zero, zero, jeden, jeden. Linia 3: jeden, zero, zero, jeden, jeden. Linia 4: jeden, jeden, jeden, zero, jeden. Linia 5: zero, jeden, jeden, jeden, zero.

R5kpLuCgI7RXv

RB5qE0QT2xJzo1

Ćwiczenie 3

Połącz w pary reprezentację z jej rozmiarem. Maicerz sąsiedztwa Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2.

| E |

par dwóch elementów, 3.

| V | \times | V |

, 4.

| V | \times | E |

Lista sąsiedztwa Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2.

| E |

par dwóch elementów, 3.

| V | \times | V |

, 4.

| V | \times | E |

Macierz incydencji Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2.

| E |

par dwóch elementów, 3.

| V | \times | V |

, 4.

| V | \times | E |

Lista krawędzi Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2.

| E |

par dwóch elementów, 3.

| V | \times | V |

, 4.

| V | \times | E |

RnInxEeBGjbfJ2

Ćwiczenie 4

R1ANMnAUVvngZ2

Ćwiczenie 5

Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Ćwiczenie 5

RPiTPEp4hCX3p

R13IwlG5Aj9Uq21

Ćwiczenie 6

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ćwiczenie 7

Dany jest graf nieskierowany bez wag. Napisz program, która przekształci macierz sąsiedztwa tego grafu w listę sąsiedztwa.

Specyfikacja problemu:

Dane:

macierz_sasiedztw – macierz liczb całkowitych

Wynik:

lista sąsiedztwa grafu

Przykładowe wyniki:

Przetestuj działanie programu dla następującej macierzy sąsiedztwa:

macierz_sasiedztwa = [
    [0, 1, 1, 1, 1],
    [1, 0, 1, 1, 1],
    [1, 1, 0, 0, 1],
    [1, 1, 0, 0, 1],
    [1, 1, 1, 1, 0]
]

R1WQeJRu96HVH

Przykładowe rozwiązanie zadania:

Linia 1. def przeksztalc otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 2. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 3. for j in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 4. if macierz podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy dwukropek. Linia 5. lista podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka append otwórz nawias okrągły j zamknij nawias okrągły. Linia 7. def wypisz otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 8. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 9. print otwórz nawias okrągły str otwórz nawias okrągły i zamknij nawias okrągły plus cudzysłów dwukropek cudzysłów przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 10. for sasiad in lista podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 11. print otwórz nawias okrągły sasiad przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 12. print otwórz nawias okrągły zamknij nawias okrągły. Linia 14. macierz podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy. Linia 15. otwórz nawias kwadratowy 0 przecinek 1 przecinek 1 przecinek 1 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 16. otwórz nawias kwadratowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 17. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 18. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 19. otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 20. zamknij nawias kwadratowy. Linia 22. n znak równości len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 24. lista podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy for podkreślnik in range otwórz nawias okrągły n zamknij nawias okrągły zamknij nawias kwadratowy. Linia 26. przeksztalc otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 27. wypisz otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły.

def przeksztalc(macierz_sasiedztwa):
    for i in range(n):
        for j in range(n):
            if macierz_sasiedztwa[i][j]:
                lista_sasiedztwa[i].append(j)

def wypisz(macierz_sasiedztwa):
    for i in range(n):
        print(str(i) + ":", end=" ")
        for sasiad in lista_sasiedztwa[i]:
            print(sasiad, end=" ")
        print()

macierz_sasiedztwa = [
    [0, 1, 1, 1, 1],
    [1, 0, 1, 1, 1],
    [1, 1, 0, 0, 1],
    [1, 1, 0, 0, 1],
    [1, 1, 1, 1, 0]
]

n = len(macierz_sasiedztwa)

lista_sasiedztwa = [[] for _ in range(n)]

przeksztalc(macierz_sasiedztwa)
wypisz(macierz_sasiedztwa)

Ćwiczenie 8

Dany jest graf nieskierowany bez wag. Napisz program, który przekształci listę sąsiedztwa danego grafu w macierz incydencji.

Specyfikacja problemu:

Dane:

lista_sasiedztwa – macierz liczb całkowitych

Wynik:

macierz incydencji grafu

Przykładowe wyniki:

1 1 1 1 0 0 0 0 0 
1 0 0 0 1 1 1 0 0 
0 1 0 0 1 0 0 1 0 
0 0 1 0 0 1 0 0 1 
0 0 0 1 0 0 1 1 1

Przetestuj działanie programu dla następującej listy sąsiedztwa:

lista_sasiedztwa = [
    [1, 2, 3, 4],
    [0, 2, 3, 4],
    [0, 1, 4],
    [0, 1, 4],
    [0, 1, 2, 3]
]

R1SD71218siIg

Przykładowe rozwiązanie zadania:

Linia 1. n znak równości 5. Linia 2. E znak równości 10. Linia 4. lista podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy. Linia 5. otwórz nawias kwadratowy 1 przecinek 2 przecinek 3 przecinek 4 zamknij nawias kwadratowy przecinek. Linia 6. otwórz nawias kwadratowy 0 przecinek 2 przecinek 3 przecinek 4 zamknij nawias kwadratowy przecinek. Linia 7. otwórz nawias kwadratowy 0 przecinek 1 przecinek 4 zamknij nawias kwadratowy przecinek. Linia 8. otwórz nawias kwadratowy 0 przecinek 1 przecinek 4 zamknij nawias kwadratowy przecinek. Linia 9. otwórz nawias kwadratowy 0 przecinek 1 przecinek 2 przecinek 3 zamknij nawias kwadratowy. Linia 10. zamknij nawias kwadratowy. Linia 12. macierz podkreślnik incydencji znak równości otwórz nawias kwadratowy otwórz nawias kwadratowy 0 for podkreślnik in range otwórz nawias okrągły E zamknij nawias okrągły zamknij nawias kwadratowy for podkreślnik in range otwórz nawias okrągły n zamknij nawias okrągły zamknij nawias kwadratowy. Linia 14. m znak równości 0. Linia 16. def przeksztalc otwórz nawias okrągły macierz podkreślnik incydencji zamknij nawias okrągły dwukropek. Linia 17. global m. Linia 18. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 19. for j in lista podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 20. if i zamknij nawias ostrokątny j dwukropek. Linia 21. continue. Linia 23. macierz podkreślnik incydencji otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy m zamknij nawias kwadratowy znak równości 1. Linia 24. macierz podkreślnik incydencji otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias kwadratowy m zamknij nawias kwadratowy znak równości 1. Linia 25. m plus znak równości 1. Linia 27. def wypisz otwórz nawias okrągły macierz podkreślnik incydencji zamknij nawias okrągły dwukropek. Linia 28. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 29. for j in range otwórz nawias okrągły m zamknij nawias okrągły dwukropek. Linia 30. print otwórz nawias okrągły macierz podkreślnik incydencji otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 31. print otwórz nawias okrągły zamknij nawias okrągły. Linia 33. przeksztalc otwórz nawias okrągły macierz podkreślnik incydencji zamknij nawias okrągły. Linia 34. wypisz otwórz nawias okrągły macierz podkreślnik incydencji zamknij nawias okrągły.

n = 5
E = 10

lista_sasiedztwa = [
    [1, 2, 3, 4],
    [0, 2, 3, 4],
    [0, 1, 4],
    [0, 1, 4],
    [0, 1, 2, 3]
]

macierz_incydencji = [[0 for _ in range(E)] for _ in range(n)]

m = 0

def przeksztalc(macierz_incydencji):
    global m
    for i in range(n):
        for j in lista_sasiedztwa[i]:
            if i > j:
                continue

            macierz_incydencji[i][m] = 1
            macierz_incydencji[j][m] = 1
            m += 1

def wypisz(macierz_incydencji):
    for i in range(n):
        for j in range(m):
            print(macierz_incydencji[i][j], end=" ")
        print()

przeksztalc(macierz_incydencji)
wypisz(macierz_incydencji)

Ćwiczenie 9

Macierze sąsiedztwa dobrze sprawdzają się w reprezentacji grafów ważonych. Jeśli wagi krawędzi są różne od 0, wówczas tam, gdzie normalnie wstawilibyśmy 1, wpiszemy wagę krawędzi. Gdyby jednak graf zawierał wagę 0, to za brak połączenia uznajemy pewną liczbę waga rożną od wszystkich wag w grafie.

Podobnie jak macierz sąsiedztwa, także lista sąsiedztwa może służyć do prezentacji grafów ważonych. W takim wypadku wyrazy na liście sąsiadów danego wierzchołka będą parą uporządkowaną dwóch elementów: indeksu sąsiada oraz wagi krawędzi łączącej sąsiada z wierzchołkiem. Przykładowo: jeśli waga krawędzi ij wynosi 5, wówczas na liście listaSasiedztwa[i] powinna znaleźć się para [j, 5]. Graf domyślnie jest nieskierowany, więc analogicznie lista lista_sasiedztwa[j] zawiera parę [i, 5].

R1b8UlEnz7IDA

Rysunek grafu i dwie różne reprezentacje: macierz sąsiedztwa, macierz incydencji — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Zdefiniowano listę krawędzi w postaci listy list składających się z trzech elementów, gdzie pierwszy i ostatni element każdej listy to indeksy sąsiednich wierzchołków, a element środkowy jest wagą krawędzi łączącej te wierzchołki. Twoim zadaniem jest zdefiniowanie następujących funkcji:

Funkcja przeksztalc_krawedzie(krawedzie), która przekształci listę krawedzie w macierz sąsiedztwa macierz_sasiedztwa w wersji ważonej.
Funkcja przeksztalc_macierz(macierz_sasiedztwa), która na podstawie macierzy sąsiedztwa macierz_sasiedztwa wstawi do listy sąsiedztwa lista_sasiedztwa sąsiadów każdego wierzchołka i.

Specyfikacja problemu:

Dane:

krawedzie – macierz liczb całkowitych

Wynik:

macierz sąsiedztwa oraz lista sąsiedztwa grafu

Przykładowe wyniki:

0 2 3 6 4 5
2 0 1 9 4 0
3 1 0 0 0 7
6 9 0 0 8 9
4 4 0 8 0 1
5 0 7 9 1 0

0: [1, 2] [2, 3] [3, 6] [4, 4] [5, 5]
1: [0, 2] [2, 1] [3, 9] [4, 4]
2: [0, 3] [1, 1] [5, 7]
3: [0, 6] [1, 9] [4, 8] [5, 9]
4: [0, 4] [1, 4] [3, 8] [5, 1]
5: [0, 5] [2, 7] [3, 9] [4, 1]

Działanie programu przetestuj dla następującej tablicy (zaimplementowanej za pomocą listy list) krawedzie:

krawedzie = [
    [1, 2, 0],
    [2, 3, 0],
    [3, 6, 0],
    [4, 4, 0],
    [5, 5, 0],
    [2, 1, 1],
    [3, 9, 1],
    [4, 4, 1],
    [5, 0, 1],
    [3, 0, 2],
    [4, 0, 2],
    [5, 7, 2],
    [4, 8, 3],
    [5, 9, 3],
    [5, 1, 4]
]

R75rvJmvkFiGU

Przykładowe rozwiązanie zadania:

Linia 1. n znak równości 6. Linia 3. krawedzie znak równości otwórz nawias kwadratowy. Linia 4. otwórz nawias kwadratowy 1 przecinek 2 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 5. otwórz nawias kwadratowy 2 przecinek 3 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 6. otwórz nawias kwadratowy 3 przecinek 6 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 7. otwórz nawias kwadratowy 4 przecinek 4 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 8. otwórz nawias kwadratowy 5 przecinek 5 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 9. otwórz nawias kwadratowy 2 przecinek 1 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 10. otwórz nawias kwadratowy 3 przecinek 9 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 11. otwórz nawias kwadratowy 4 przecinek 4 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 12. otwórz nawias kwadratowy 5 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 13. otwórz nawias kwadratowy 3 przecinek 0 przecinek 2 zamknij nawias kwadratowy przecinek. Linia 14. otwórz nawias kwadratowy 4 przecinek 0 przecinek 2 zamknij nawias kwadratowy przecinek. Linia 15. otwórz nawias kwadratowy 5 przecinek 7 przecinek 2 zamknij nawias kwadratowy przecinek. Linia 16. otwórz nawias kwadratowy 4 przecinek 8 przecinek 3 zamknij nawias kwadratowy przecinek. Linia 17. otwórz nawias kwadratowy 5 przecinek 9 przecinek 3 zamknij nawias kwadratowy przecinek. Linia 18. otwórz nawias kwadratowy 5 przecinek 1 przecinek 4 zamknij nawias kwadratowy. Linia 19. zamknij nawias kwadratowy. Linia 21. def przeksztalc podkreślnik krawedzie otwórz nawias okrągły krawedzie zamknij nawias okrągły dwukropek. Linia 22. macierz podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk n for podkreślnik in range otwórz nawias okrągły n zamknij nawias okrągły zamknij nawias kwadratowy. Linia 23. for krawedz in krawedzie dwukropek. Linia 24. macierz podkreślnik sasiedztwa otwórz nawias kwadratowy krawedz otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy krawedz otwórz nawias kwadratowy 2 zamknij nawias kwadratowy zamknij nawias kwadratowy znak równości krawedz otwórz nawias kwadratowy 1 zamknij nawias kwadratowy. Linia 25. macierz podkreślnik sasiedztwa otwórz nawias kwadratowy krawedz otwórz nawias kwadratowy 2 zamknij nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy krawedz otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias kwadratowy znak równości krawedz otwórz nawias kwadratowy 1 zamknij nawias kwadratowy. Linia 26. return macierz podkreślnik sasiedztwa. Linia 28. def przeksztalc podkreślnik macierz otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 29. lista podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy for podkreślnik in range otwórz nawias okrągły n zamknij nawias okrągły zamknij nawias kwadratowy. Linia 30. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 31. for j in range otwórz nawias okrągły i plus 1 przecinek n zamknij nawias okrągły dwukropek. Linia 32. if macierz podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy wykrzyknik znak równości 0 dwukropek. Linia 33. lista podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka append otwórz nawias okrągły otwórz nawias okrągły j przecinek macierz podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły. Linia 34. lista podkreślnik sasiedztwa otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka append otwórz nawias okrągły otwórz nawias okrągły i przecinek macierz podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły. Linia 35. return lista podkreślnik sasiedztwa. Linia 37. def wypisz podkreślnik macierz otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 38. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 39. print otwórz nawias okrągły cudzysłów cudzysłów kropka join otwórz nawias okrągły str otwórz nawias okrągły x zamknij nawias okrągły for x in macierz podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły. Linia 41. def wypisz podkreślnik lista otwórz nawias okrągły lista podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 42. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 43. sasiedzi znak równości otwórz nawias kwadratowy cudzysłów otwórz nawias kwadratowy cudzysłów plus str otwórz nawias okrągły sasiad otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły plus cudzysłów przecinek cudzysłów plus str otwórz nawias okrągły sasiad otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły plus cudzysłów zamknij nawias kwadratowy cudzysłów for sasiad in lista podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy. Linia 44. print otwórz nawias okrągły str otwórz nawias okrągły i zamknij nawias okrągły plus cudzysłów dwukropek cudzysłów plus apostrof apostrof kropka join otwórz nawias okrągły sasiedzi zamknij nawias okrągły zamknij nawias okrągły. Linia 46. macierz podkreślnik sasiedztwa znak równości przeksztalc podkreślnik krawedzie otwórz nawias okrągły krawedzie zamknij nawias okrągły. Linia 47. wypisz podkreślnik macierz otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 48. print otwórz nawias okrągły zamknij nawias okrągły. Linia 50. lista podkreślnik sasiedztwa znak równości przeksztalc podkreślnik macierz otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 51. wypisz podkreślnik lista otwórz nawias okrągły lista podkreślnik sasiedztwa zamknij nawias okrągły.

n = 6

krawedzie = [
    [1, 2, 0],
    [2, 3, 0],
    [3, 6, 0],
    [4, 4, 0],
    [5, 5, 0],
    [2, 1, 1],
    [3, 9, 1],
    [4, 4, 1],
    [5, 0, 1],
    [3, 0, 2],
    [4, 0, 2],
    [5, 7, 2],
    [4, 8, 3],
    [5, 9, 3],
    [5, 1, 4]
]

def przeksztalc_krawedzie(krawedzie):
    macierz_sasiedztwa = [[0]*n for _ in range(n)]
    for krawedz in krawedzie:
        macierz_sasiedztwa[krawedz[0]][krawedz[2]] = krawedz[1]
        macierz_sasiedztwa[krawedz[2]][krawedz[0]] = krawedz[1]
    return macierz_sasiedztwa

def przeksztalc_macierz(macierz_sasiedztwa):
    lista_sasiedztwa = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            if macierz_sasiedztwa[i][j] != 0:
                lista_sasiedztwa[i].append((j, macierz_sasiedztwa[i][j]))
                lista_sasiedztwa[j].append((i, macierz_sasiedztwa[i][j]))
    return lista_sasiedztwa

def wypisz_macierz(macierz_sasiedztwa):
    for i in range(n):
        print(" ".join(str(x) for x in macierz_sasiedztwa[i]))

def wypisz_lista(lista_sasiedztwa):
    for i in range(n):
        sasiedzi = ["[" + str(sasiad[0]) + ", " + str(sasiad[1]) + "]" for sasiad in lista_sasiedztwa[i]]
        print(str(i) + ": " + ' '.join(sasiedzi))

macierz_sasiedztwa = przeksztalc_krawedzie(krawedzie)
wypisz_macierz(macierz_sasiedztwa)
print()

lista_sasiedztwa = przeksztalc_macierz(macierz_sasiedztwa)
wypisz_lista(lista_sasiedztwa)

Prezentacja multimedialna

Dla nauczyciela