Sprawdź się

Pokaż ćwiczenia:

R1ayjYdSmwhoj1

Ćwiczenie 1

Możliwe odpowiedzi: 1. Nie ujemna, 2. Różna od 0, 3. Różna od dowolonej liczby ujemnej

RFbzfQEhMarcH1

Ćwiczenie 2

Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.

R6N0QS1fwWHQ62

Ćwiczenie 3

Dostępne opcje do wyboru:

t

s

w

f

. Polecenie: Jeśli w sieci przepływowej

s

jest źródłem, a

t

ujściem to przepływ

| f |

tej sieci spełnia równanie.

| f | = \sum_{w \in V} f (

luka do uzupełnienia

, w) = \sum_{w \in V} f (

luka do uzupełnienia

, t)

Dostępne opcje do wyboru:

t

s

w

f

. Polecenie: Jeśli w sieci przepływowej

s

jest źródłem, a

t

ujściem to przepływ

| f |

tej sieci spełnia równanie.

| f | = \sum_{w \in V} f (

luka do uzupełnienia

, w) = \sum_{w \in V} f (

luka do uzupełnienia

, t)

R18Yp3wK6607Q21

Ćwiczenie 4

Wymyśl pytanie na kartkówkę związane z tematem materiału.

R1UkoFDoIg9YP2

Ćwiczenie 5

Ile równa jest spójność krawędziowa grafu pełnego o

| V |

wierzchołkach? Możliwe odpowiedzi: 1.

| V | - 1

, 2.

| V |

, 3.

| E | - 1

, 4.

| E |

RXzpobiJ2dVsD2

Ćwiczenie 6

Sieć przepływową reprezentuje nasępująca ważona macierz sąsiedztwa

A = [\begin{matrix} 0 & 4 & 7 & 9 & 0 \\ 0 & 0 & 0 & 3 & 11 \\ 1 & 4 & 0 & 8 & 2 \\ 0 & 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}]

W sieci, którą reprezentuje powyższa ważona macierz sąsiedztwa (wagi to przepustowość krawędzi skierowanej) maksymalny przepływ ze źródła w 2 i ujściu w wierzchołku 3 wynosi Tu uzupełnij.

Sieć przepływową reprezentuje nasępująca ważona macierz sąsiedztwa

A = [\begin{matrix} 0 & 4 & 7 & 9 & 0 \\ 0 & 0 & 0 & 3 & 11 \\ 1 & 4 & 0 & 8 & 2 \\ 0 & 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}]

Ćwiczenie 7

Sprawdź działanie algorytmu Forda‑Fulkersona dla przedstawionej sieci przepływowej, by wskazać, ile wynosi maksymalny przepływ od zaznaczonego źródła do ujścia w tej sieci. Wskaż prawidłową odpowiedź.

R1OyBNV7iDbic

Ilustracja przedstawia sieć składającą się z ośmiu punktów od zero do sześć, gdzie zero to źródło, a sześć to ujście. Pomiędzy punktami znajdują się strzałki z następującymi wartościami. Pomiędzy zero i jeden wartość 11, pomiędzy zero i trzy wartość 14, pomiędzy jeden i dwa wartość 10, pomiędzy jeden i cztery wartość 9, pomiędzy dwa i cztery wartość 7, pomiędzy trzy i cztery wartość 5, pomiędzy trzy i pięć wartość 8, pomiędzy pięć i sześć wartość 1, pomiędzy cztery i sześć wartość 9, pomiędzy cztery i siedem wartość 9, pomiędzy siedem i sześć wartość 7 . — Sieć przepływowa danego grafu składającego się z ośmiu wierzchołków oraz 11 krawędzi. Źródłem tej sieci jest wierzchołek oznaczony jako 0, jej ujściem wierzchołek oznaczony jako 6.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

R100dRlwL1Lf1

Możliwe odpowiedzi: 1. Prawidłowa odpowiedź, 2. Nieprawidłowa odpowiedź A, 3. Nieprawidłowa odpowiedź B

Ćwiczenie 8

RK8ZWmCcs0Wqr

RoscoAnFR0QoG

Przykładowe wartości dla kolejnych krawędzi:

$f(0,1) = 11$
$f(0,3) = 6$
$f(1,2) = 2$
$f(1,4) = 9$
$f(2,4) = 2$
$f(3,4) = 5$
$f(3,5) = 1$
$f(4,6) = 9$
$f(4,7) = 7$
$f(5,6) = 1$
$f(7,6) = 7$

Aplet

Dla nauczyciela

Sprawdź się