ZESTAW 1 Boruszko R. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {b, g}, {a, g}, {a, h}, {b, h}, {g, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

660

460

520

540

260

650

B

-

250

460

660

250

460

C

-

260

560

420

640

D

-

650

640

460

E

-

420

460

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

1

ZESTAW 2 Dąbek D. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {c, g}, {b, g}, {d, g}, {c, f }, {d, h}, {e, h}, {b, b}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

560

240

450

750

550

470

B

-

540

340

450

540

340

C

-

560

450

350

450

D

-

570

650

260

E

-

250

360

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

2

ZESTAW 3 Dobrowolski D. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {b, d}, {b, g}, {d, g}, {a, h}, {d, h}, {e, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

750

450

430

570

370

550

B

-

340

450

570

340

450

C

-

350

470

430

570

D

-

750

570

450

E

-

430

450

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

3

ZESTAW 4 Góraj G. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, e}, {b, d}, {d, f }, {d, g}, {a, h}, {b, h}, {e, h}, {a, a}, {c, c}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

450

720

670

730

740

270

B

-

760

520

240

760

520

C

-

750

640

570

230

D

-

470

530

750

E

-

770

550

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

4

ZESTAW 5 Gniado A. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {c, g}, {b, g}, {a, g}, {c, f }, {b, h}, {e, h}, {b, b}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

540

640

340

370

450

430

B

-

430

440

450

430

440

C

-

440

350

440

470

D

-

530

470

640

E

-

640

440

F

-

490

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

5

ZESTAW 6 Juda Ł. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, e}, {c, g}, {d, f }, {a, g}, {c, f }, {d, h}, {g, h}, {b, b}, {c, c}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

220

220

270

430

720

240

B

-

720

420

220

720

420

C

-

720

220

470

230

D

-

240

230

220

E

-

270

420

F

-

290

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

6

ZESTAW 7 Kędziorek K. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, e}, {c, g}, {b, g}, {d, g}, {a, h}, {d, h}, {g, h}, {b, b}, {d, d}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

320

740

470

570

730

450

B

-

740

540

430

740

540

C

-

720

430

570

470

D

-

350

270

720

E

-

770

520

F

-

290

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

7

ZESTAW 8 Kępka R. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {b, d}, {b, g}, {a, g}, {a, h}, {d, h}, {g, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

370

450

260

450

630

540

B

-

620

250

530

620

250

C

-

670

230

260

550

D

-

340

750

470

E

-

460

270

F

-

790

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

8

ZESTAW 9 Kałużniak M. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {b, d}, {b, g}, {a, g}, {c, f }, {b, h}, {g, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

660

270

520

370

260

730

B

-

250

770

760

250

770

C

-

260

560

720

770

D

-

630

670

260

E

-

220

760

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

9

ZESTAW 10 Kawa R. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, e}, {c, g}, {d, f }, {d, g}, {c, f }, {d, h}, {e, h}, {a, a}, {d, d}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

450

620

450

450

540

240

B

-

540

420

240

540

420

C

-

550

440

450

250

D

-

440

550

650

E

-

650

450

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

10

ZESTAW 11 Kozioł R. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, e}, {c, g}, {d, f }, {a, g}, {a, h}, {d, h}, {e, h}, {b, b}, {c, c}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

720

560

530

340

370

630

B

-

350

560

670

350

560

C

-

320

570

530

640

D

-

730

240

520

E

-

530

520

F

-

290

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

11

ZESTAW 12 Krawczyk K. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {b, d}, {d, f }, {a, g}, {a, h}, {b, h}, {g, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

430

720

360

640

640

260

B

-

630

520

240

630

520

C

-

630

340

560

240

D

-

460

340

730

E

-

760

530

F

-

390

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

12

ZESTAW 13 Krupiński Ł. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {b, g}, {a, g}, {a, h}, {b, h}, {g, h}, {a, a}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

340

630

640

540

430

350

B

-

460

230

330

460

230

C

-

440

630

240

340

D

-

350

440

640

E

-

640

240

F

-

490

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

13

ZESTAW 14 Kuźniewski Ł. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {b, d}, {b, g}, {d, g}, {c, f }, {d, h}, {g, h}, {b, b}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

770

440

360

540

670

450

B

-

630

340

470

630

340

C

-

670

370

360

440

D

-

750

740

470

E

-

460

370

F

-

790

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

14

ZESTAW 15 Kwiatkowski J. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {b, d}, {d, f }, {d, g}, {c, f }, {b, h}, {g, h}, {a, a}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

750

770

630

570

370

750

B

-

360

470

770

360

470

C

-

350

670

430

770

D

-

750

570

750

E

-

730

450

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

15

ZESTAW 16 Lipiński P. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {b, d}, {d, f }, {d, g}, {a, h}, {b, h}, {g, h}, {a, a}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

460

550

450

520

540

550

B

-

540

350

540

540

350

C

-

560

440

350

520

D

-

450

620

560

E

-

550

360

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

16

ZESTAW 17 Małetko P. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, e}, {c, g}, {d, f }, {d, g}, {c, f }, {d, h}, {g, h}, {a, a}, {c, c}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

350

670

430

560

330

750

B

-

340

570

730

340

570

C

-

350

430

530

760

D

-

350

560

650

E

-

630

550

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

17

ZESTAW 18 Macewicz C. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, e}, {c, g}, {d, f }, {d, g}, {a, h}, {b, h}, {g, h}, {b, b}, {c, c}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

330

670

360

540

630

750

B

-

630

670

730

630

670

C

-

630

330

660

740

D

-

350

340

630

E

-

660

630

F

-

390

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

18

ZESTAW 19 Mucha M. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, e}, {c, g}, {d, f }, {d, g}, {c, f }, {b, h}, {g, h}, {a, a}, {c, c}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

720

570

230

540

370

750

B

-

320

670

770

320

670

C

-

320

270

630

740

D

-

750

240

520

E

-

530

620

F

-

290

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

19

ZESTAW 20 Pałka W. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {b, d}, {b, g}, {a, g}, {a, h}, {b, h}, {g, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

650

240

770

350

760

430

B

-

770

440

460

770

440

C

-

750

760

470

450

D

-

630

550

250

E

-

270

450

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

20

ZESTAW 21 Piórek K. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {d, f }, {d, g}, {c, f }, {b, h}, {g, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

330

440

320

730

230

470

B

-

230

540

430

230

540

C

-

230

330

520

430

D

-

370

330

430

E

-

420

530

F

-

390

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

21

ZESTAW 22 Pobocha M. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {d, f }, {d, g}, {c, f }, {b, h}, {g, h}, {a, a}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

270

550

260

230

620

520

B

-

620

750

520

620

750

C

-

670

220

760

530

D

-

220

730

570

E

-

560

770

F

-

790

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

22

ZESTAW 23 Popko K. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {b, d}, {b, g}, {a, g}, {c, f }, {b, h}, {g, h}, {a, a}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

740

530

670

330

770

330

B

-

760

230

370

760

230

C

-

740

670

270

330

D

-

730

430

540

E

-

570

240

F

-

490

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

23

ZESTAW 24 Prawdzik P. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {b, g}, {a, g}, {a, h}, {b, h}, {g, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

460

760

620

670

240

660

B

-

260

460

640

260

460

C

-

260

640

420

670

D

-

460

670

760

E

-

720

460

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

24

ZESTAW 25 Prysak K. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {d, f }, {d, g}, {a, h}, {b, h}, {e, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

240

620

570

560

720

250

B

-

750

420

220

750

420

C

-

740

520

470

260

D

-

250

460

640

E

-

670

440

F

-

490

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

25

ZESTAW 26 Raginis S. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {c, g}, {b, g}, {a, g}, {c, f }, {d, h}, {e, h}, {b, b}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

470

570

520

630

240

760

B

-

250

570

740

250

570

C

-

270

540

520

730

D

-

460

730

570

E

-

520

570

F

-

790

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

26

ZESTAW 27 Regulski J. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, e}, {b, d}, {d, f }, {d, g}, {a, h}, {d, h}, {g, h}, {b, b}, {d, d}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

520

520

530

730

350

270

B

-

350

220

250

350

220

C

-

320

550

230

230

D

-

570

230

520

E

-

530

220

F

-

290

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

27

ZESTAW 28 Rosochacki B. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {c, g}, {d, f }, {d, g}, {c, f }, {b, h}, {e, h}, {a, a}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

760

330

440

760

470

370

B

-

440

430

370

440

430

C

-

460

470

440

360

D

-

770

660

360

E

-

340

460

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

28

ZESTAW 29 Sobczak Ł. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, e}, {b, d}, {b, g}, {d, g}, {a, h}, {d, h}, {g, h}, {b, b}, {d, d}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

260

370

440

750

420

770

B

-

440

270

720

440

270

C

-

460

420

240

750

D

-

270

650

360

E

-

340

260

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

29

ZESTAW 30 Ulaniuk D. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {b, g}, {a, g}, {a, h}, {d, h}, {e, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

320

520

340

620

430

260

B

-

430

620

230

430

620

C

-

420

330

640

220

D

-

360

220

520

E

-

540

620

F

-

290

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

30

ZESTAW 31 Voznyak A. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {b, d}, {d, f }, {a, g}, {a, h}, {d, h}, {g, h}, {b, b}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

750

520

470

220

770

220

B

-

740

420

270

740

420

C

-

750

470

470

220

D

-

720

520

550

E

-

570

450

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

31

ZESTAW 32 Voznyak J. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {b, d}, {d, f }, {a, g}, {a, h}, {d, h}, {e, h}, {b, b}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

660

760

340

430

460

640

B

-

430

760

660

430

760

C

-

460

360

740

630

D

-

640

630

760

E

-

740

760

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

32

ZESTAW 33 Wójcik K. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {d, f }, {d, g}, {a, h}, {d, h}, {e, h}, {a, a}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

750

470

670

260

770

720

B

-

760

370

770

760

370

C

-

750

670

370

760

D

-

720

560

450

E

-

470

350

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

33

ZESTAW 34 Wójcik S. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {c, g}, {d, f }, {a, g}, {a, h}, {b, h}, {g, h}, {b, b}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

350

240

260

560

630

450

B

-

620

640

430

620

640

C

-

650

230

660

460

D

-

350

560

250

E

-

260

650

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

34

ZESTAW 35 Warda K. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {d, f }, {a, g}, {c, f }, {b, h}, {e, h}, {a, a}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

760

340

450

540

570

450

B

-

540

440

470

540

440

C

-

560

470

450

440

D

-

750

640

360

E

-

350

460

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

35

ZESTAW 36 Wiercioch P. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {c, g}, {d, f }, {a, g}, {a, h}, {b, h}, {e, h}, {b, b}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

730

240

270

220

770

420

B

-

720

240

470

720

240

C

-

730

270

270

420

D

-

720

320

230

E

-

270

230

F

-

390

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

36

ZESTAW 37 Woźniakowski A. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, e}, {b, d}, {b, g}, {a, g}, {a, h}, {d, h}, {g, h}, {b, b}, {c, c}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

740

540

230

530

370

450

B

-

320

740

470

320

740

C

-

340

270

730

430

D

-

750

430

540

E

-

530

740

F

-

490

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

37

ZESTAW 38 Wodecki B. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {d, f }, {d, g}, {c, f }, {d, h}, {e, h}, {a, a}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

760

240

650

240

570

420

B

-

560

740

470

560

740

C

-

560

670

750

440

D

-

720

640

260

E

-

250

760

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

38

ZESTAW 39 Zasłona M. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, e}, {c, g}, {d, f }, {a, g}, {c, f }, {d, h}, {g, h}, {b, b}, {c, c}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

730

660

240

220

470

620

B

-

420

660

670

420

660

C

-

430

270

640

620

D

-

720

320

630

E

-

640

630

F

-

390

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

39

ZESTAW 40 Zwoliński B. .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, e}, {c, g}, {d, f }, {a, g}, {a, h}, {b, h}, {g, h}, {a, a}, {d, d}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

470

720

640

240

440

220

B

-

460

220

240

460

220

C

-

470

640

240

240

D

-

420

740

770

E

-

740

270

F

-

790

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

40

ZESTAW 41 .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {c, g}, {d, f }, {a, g}, {a, h}, {b, h}, {e, h}, {b, b}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

730

720

560

760

670

270

B

-

650

220

270

650

220

C

-

630

570

260

260

D

-

770

360

730

E

-

760

230

F

-

390

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

41

ZESTAW 42 .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, e}, {c, g}, {d, f }, {d, g}, {c, f }, {b, h}, {e, h}, {b, b}, {d, d}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

470

340

670

760

740

470

B

-

760

440

440

760

440

C

-

770

640

470

460

D

-

470

760

370

E

-

370

470

F

-

790

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

42

ZESTAW 43 .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {b, d}, {d, f }, {d, g}, {c, f }, {d, h}, {e, h}, {a, a}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

270

720

770

350

720

230

B

-

770

420

220

770

420

C

-

770

720

470

250

D

-

230

750

770

E

-

770

470

F

-

790

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

43

ZESTAW 44 .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {b, g}, {a, g}, {c, f }, {d, h}, {g, h}, {b, b}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

730

460

670

320

770

630

B

-

760

360

670

760

360

C

-

730

670

370

620

D

-

730

320

430

E

-

470

330

F

-

390

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

44

ZESTAW 45 .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, e}, {b, d}, {d, f }, {d, g}, {c, f }, {d, h}, {e, h}, {b, b}, {d, d}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

250

530

240

370

420

330

B

-

420

430

320

420

430

C

-

450

220

440

370

D

-

230

570

550

E

-

540

450

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

45

ZESTAW 46 .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, e}, {b, d}, {b, g}, {a, g}, {c, f }, {d, h}, {g, h}, {b, b}, {c, c}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

360

670

320

220

230

720

B

-

230

370

730

230

370

C

-

260

330

320

720

D

-

320

620

660

E

-

620

360

F

-

690

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

46

ZESTAW 47 .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, f }, {c, g}, {d, f }, {d, g}, {c, f }, {d, h}, {e, h}, {a, a}, {d, d}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

750

440

420

640

270

460

B

-

240

440

470

240

440

C

-

250

470

420

440

D

-

760

540

450

E

-

420

450

F

-

590

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

47

ZESTAW 48 .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, f }, {c, g}, {d, f }, {d, g}, {c, f }, {d, h}, {g, h}, {b, b}, {c, c}, {f, f }. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

720

440

760

320

670

430

B

-

670

540

470

670

540

C

-

620

770

560

420

D

-

730

220

420

E

-

460

520

F

-

290

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

48

ZESTAW 49 .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, c}, {a, e}, {c, g}, {b, g}, {a, g}, {c, f }, {b, h}, {e, h}, {b, b}, {c, c}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

220

460

240

260

420

620

B

-

420

360

620

420

360

C

-

420

220

340

660

D

-

220

260

420

E

-

440

320

F

-

290

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

49

ZESTAW 50 .

1. Graf nieskierowany G składa się z wierzchołków a, b, c, d, e, f , g, h oraz krawędzi {a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {f, g},
{g, h}, {a, d}, {a, e}, {c, g}, {b, g}, {a, g}, {a, h}, {d, h}, {e, h}, {b, b}, {d, d}, {e, e}. a) Wyznacz macierz sąsiedztwa tego grafu.
b) Stosując algorytm DRZEWO SPINAJĄCE utwórz drzewo spinające tego grafu. c) Wyznacz liście tego drzewa. d) Wyznacz
macierz sąsiedztwa tego drzewa.

2. Gmina skladająca się z miejscowości A, B, C, D, E, F , G planuje budowę sieci kanalizacyjnej. Ze względu na różne ukształ-
towania terenu koszty (w tys. zł) budowy kanalizacji pomiędzy poszczególnymi wioskami podane są tabeli:

A

B

C

D

E

F

G

A

-

730

460

720

650

270

660

B

-

270

260

670

270

260

C

-

230

770

220

650

D

-

760

350

430

E

-

420

230

F

-

390

G

-

Stosując algorytm Kruskala wyznacz sposób najtańszej realizacji tego projektu.

50