Sprawdź się

Pokaż ćwiczenia:

R9yqKb7JKEWq71

Ćwiczenie 1

RqMUv4CAn0eiK2

Ćwiczenie 2

Ile spójnych składowych może mieć graf nieskierowany bez pętli i krwędzi wielokrotnych o 6 wierzchołkach i następującym ciągu stopni wierzchołków.

2, 2, 2, 2, 2, 2 Możliwe odpowiedzi: 1. 1, 2. 2, 3. 3, 4. 6

R34xTehBMxpYX1

Ćwiczenie 3

RobNyF0oGKt0S11

Ćwiczenie 4

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

Ćwiczenie 5

Napisz program, który obliczy liczbę spójnych składowych grafu nieskierowanego, a następnie ją wyświetli.

Specyfikacja problemu:

Dane:

macierzSasiedztwa – macierz sąsiedztwa grafu; lista dwuwymiarowa liczb naturalnych

Wynik:

liczba spójnych składowych grafu; liczba naturalna

Działanie programu przetestuj dla następujących danych:

Graf:

RHBbzJCeoL0tO

Macierz sąsiedztwa tego grafu:

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

Przykładowy wynik dla podanych danych:

Liczba spojnych skladowych grafu: 3

R1Gw013JDcmB3

Linia 1. macierz podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy. Linia 2. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 3. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 4. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 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 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 7. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 8. zamknij nawias kwadratowy. Linia 10. n znak równości len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 12. def przeszukaj otwórz nawias okrągły v przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 13. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości True. Linia 14. for i in range otwórz nawias okrągły len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 15. if macierz podkreślnik sasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 1 and not odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 16. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 18. def liczba podkreślnik skladowych otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 19. odwiedzone znak równości otwórz nawias kwadratowy False zamknij nawias kwadratowy asterysk len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 20. licznik podkreślnik skladowych znak równości 0. Linia 22. for i in range otwórz nawias okrągły len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 23. if not odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 24. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 25. licznik podkreślnik skladowych plus znak równości 1. Linia 27. return licznik podkreślnik skladowych. Linia 29. print otwórz nawias okrągły cudzysłów Liczba spojnych skladowych grafu dwukropek cudzysłów przecinek liczba podkreślnik skladowych otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły zamknij nawias okrągły.

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

n = len(macierz_sasiedztwa)
    
def przeszukaj(v, odwiedzone, macierz_sasiedztwa):
    odwiedzone[v] = True
    for i in range(len(macierz_sasiedztwa)):
        if macierz_sasiedztwa[v][i] == 1 and not odwiedzone[i]:
            przeszukaj(i, odwiedzone, macierz_sasiedztwa)

def liczba_skladowych(macierz_sasiedztwa):
    odwiedzone = [False] * len(macierz_sasiedztwa)
    licznik_skladowych = 0

    for i in range(len(macierz_sasiedztwa)):
        if not odwiedzone[i]:
            przeszukaj(i, odwiedzone, macierz_sasiedztwa)
            licznik_skladowych += 1

    return licznik_skladowych

print("Liczba spojnych skladowych grafu:", liczba_skladowych(macierz_sasiedztwa))

Ćwiczenie 6

Napisz program, który sprawdzi, czy dana para wierzchołków o indeksach v oraz w tworzących krawędź vw grafu spójnego nieskierowanego reprezentowanego przez macierz sąsiedztwa jest mostem.

Specyfikacja problemu:

Dane:

macierzSasiedztwa – macierz sąsiedztwa grafu; lista dwuwymiarowa liczb naturalnych
v – indeks wierzchołka tworzącego krawędź; liczba naturalna
w – indeks wierzchołka tworzącego krawędź; liczba naturalna

Wynik:

komunikat informujący o tym, czy krawędź tworzona przez dwa podane wierzchołki vw jest mostem

Działanie programu przetestuj dla następujących danych:

Graf:

RiOppoLhKXNb6

Macierz sąsiedztwa grafu:

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

v = 0
w = 7

Przykładowy wynik dla podanych danych:

Krawedz 0-7 jest mostem

RAX4M2jwivnuO

Linia 1. macierz podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy. Linia 2. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 3. otwórz nawias kwadratowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 4. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 5. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 6. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 7. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 8. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 9. otwórz nawias kwadratowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 10. zamknij nawias kwadratowy. Linia 12. v znak równości 0. Linia 13. w znak równości 7. Linia 15. n znak równości len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 17. def przeszukaj otwórz nawias okrągły v przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 18. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości True. Linia 19. for i in range otwórz nawias okrągły len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 20. if macierz podkreślnik sasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 1 and not odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 21. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 23. def liczba podkreślnik skladowych otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 25. odwiedzone znak równości otwórz nawias kwadratowy False zamknij nawias kwadratowy asterysk n. Linia 26. licznik podkreślnik skladowych znak równości 0. Linia 28. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 29. if not odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 30. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 31. licznik podkreślnik skladowych plus znak równości 1. Linia 33. return licznik podkreślnik skladowych. Linia 35. def czy podkreślnik most otwórz nawias okrągły v przecinek w przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 36. macierz podkreślnik sasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości 0. Linia 37. macierz podkreślnik sasiedztwa otwórz nawias kwadratowy w zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości 0. Linia 38. nowa podkreślnik liczba znak równości liczba podkreślnik skladowych otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 39. macierz podkreślnik sasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości 1. Linia 40. macierz podkreślnik sasiedztwa otwórz nawias kwadratowy w zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości 1. Linia 41. liczba znak równości liczba podkreślnik skladowych otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 43. return liczba wykrzyknik znak równości nowa podkreślnik liczba. Linia 45. wynik znak równości cudzysłów Krawedz cudzysłów plus str otwórz nawias okrągły v zamknij nawias okrągły plus cudzysłów minus cudzysłów plus str otwórz nawias okrągły w zamknij nawias okrągły plus cudzysłów cudzysłów. Linia 46. if czy podkreślnik most otwórz nawias okrągły v przecinek w przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 47. wynik plus znak równości cudzysłów jest mostem cudzysłów. Linia 48. else dwukropek. Linia 49. wynik plus znak równości cudzysłów nie jest mostem cudzysłów. Linia 51. print otwórz nawias okrągły wynik zamknij nawias okrągły.

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

v = 0
w = 7

n = len(macierz_sasiedztwa)

def przeszukaj(v, odwiedzone, macierz_sasiedztwa):
    odwiedzone[v] = True
    for i in range(len(macierz_sasiedztwa)):
        if macierz_sasiedztwa[v][i] == 1 and not odwiedzone[i]:
            przeszukaj(i, odwiedzone, macierz_sasiedztwa)

def liczba_skladowych(macierz_sasiedztwa):
    
    odwiedzone = [False] * n
    licznik_skladowych = 0

    for i in range(n):
        if not odwiedzone[i]:
            przeszukaj(i, odwiedzone, macierz_sasiedztwa)
            licznik_skladowych += 1

    return licznik_skladowych

def czy_most(v, w, macierz_sasiedztwa):
    macierz_sasiedztwa[v][w] = 0
    macierz_sasiedztwa[w][v] = 0
    nowa_liczba = liczba_skladowych(macierz_sasiedztwa)
    macierz_sasiedztwa[v][w] = 1
    macierz_sasiedztwa[w][v] = 1
    liczba = liczba_skladowych(macierz_sasiedztwa)

    return liczba != nowa_liczba

wynik = "Krawedz " + str(v) + "-" + str(w) + " "
if czy_most(v, w, macierz_sasiedztwa):
    wynik += "jest mostem"
else:
    wynik += "nie jest mostem"

print(wynik)

Dla zainteresowanych

Ćwiczenie 7

Napisz program, który sprawdzi, czy dla danego digrafu reprezentowanego przez macierz sąsiedztwa możliwe jest dojście z wierzchołka startowego (o indeksie startowy) do wierzchołka końcowego (o indeksie koncowy).

Specyfikacja problemu:

Dane:

macierzSasiedztwa – macierz sąsiedztwa grafu; lista dwuwymiarowa liczb naturalnych
startowy – indeks wierzchołka; liczba naturalna
koncowy – indeks wierzchołka; liczba naturalna

Wynik:

komunikat informujący o tym, czy możliwe jest dojście z wierzchołka startowy do wierzchołka koncowy

Działanie programu przetestuj dla następujących danych:

Graf:

R1ACJIqAG7ZTa

Macierz sąsiedztwa grafu:

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

startowy = 0
koncowy = 4

Przykładowy wynik dla podanych danych:

Wierzcholek 4 jest osiagalny z wierzcholka 0

R1VXiJiHU6xJ6

Linia 1. macierz podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy. Linia 2. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 3. otwórz nawias kwadratowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 4. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 5. otwórz nawias kwadratowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 6. otwórz nawias kwadratowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 7. zamknij nawias kwadratowy. Linia 9. n znak równości len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 11. startowy znak równości 0. Linia 12. koncowy znak równości 4. Linia 14. def przeszukaj otwórz nawias okrągły v przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa przecinek docelowy zamknij nawias okrągły dwukropek. Linia 15. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości True. Linia 16. if v znak równości znak równości docelowy dwukropek. Linia 17. return True. Linia 19. for w in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 20. if macierz podkreślnik sasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości znak równości 1 and not odwiedzone otwórz nawias kwadratowy w zamknij nawias kwadratowy dwukropek. Linia 21. if przeszukaj otwórz nawias okrągły w przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa przecinek docelowy zamknij nawias okrągły dwukropek. Linia 22. return True. Linia 24. return False. Linia 26. def czy podkreślnik osiagalny otwórz nawias okrągły macierz podkreślnik sasiedztwa przecinek startowy przecinek koncowy zamknij nawias okrągły dwukropek. Linia 27. odwiedzone znak równości otwórz nawias kwadratowy False zamknij nawias kwadratowy asterysk n. Linia 28. return przeszukaj otwórz nawias okrągły startowy przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa przecinek koncowy zamknij nawias okrągły. Linia 30. if czy podkreślnik osiagalny otwórz nawias okrągły macierz podkreślnik sasiedztwa przecinek startowy przecinek koncowy zamknij nawias okrągły dwukropek. Linia 31. print otwórz nawias okrągły cudzysłów Wierzcholek cudzysłów przecinek koncowy przecinek cudzysłów jest osiagalny z wierzcholka cudzysłów przecinek startowy zamknij nawias okrągły. Linia 32. else dwukropek. Linia 33. print otwórz nawias okrągły cudzysłów Wierzcholek cudzysłów przecinek koncowy przecinek cudzysłów nie jest osiagalny z wierzcholka cudzysłów przecinek startowy zamknij nawias okrągły.

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

n = len(macierz_sasiedztwa)

startowy = 0
koncowy = 4

def przeszukaj(v, odwiedzone, macierz_sasiedztwa, docelowy):
    odwiedzone[v] = True
    if v == docelowy:
        return True

    for w in range(n):
        if macierz_sasiedztwa[v][w] == 1 and not odwiedzone[w]:
            if przeszukaj(w, odwiedzone, macierz_sasiedztwa, docelowy):
                return True

    return False

def czy_osiagalny(macierz_sasiedztwa, startowy, koncowy):
    odwiedzone = [False] * n
    return przeszukaj(startowy, odwiedzone, macierz_sasiedztwa, koncowy)

if czy_osiagalny(macierz_sasiedztwa, startowy, koncowy):
    print("Wierzcholek", koncowy, "jest osiagalny z wierzcholka", startowy)
else:
    print("Wierzcholek", koncowy, "nie jest osiagalny z wierzcholka", startowy)

Prezentacja multimedialna

Dla nauczyciela