Základní teorie grafů a její aplikace

Teorie grafů - Michal Brejcha 1

Základní teorie grafů a její aplikace

Michal Brejcha


Obsah prezentace

• Základní pojmy v teorii o grafech

• Úlohy a prohledávání grafů

• Hledání nejkratších cest


Základní pojmy

Vrchol grafu: {množina V}Je to styčná vazba v grafu, nazývá se též uzlem, prvkem nebo bodem v grafu.

Hrana grafu: {množina E}

Reprezentuje spojení jednotlivých vrcholů. Toto spojení vyjadřuje nějaký vztah mezi vrcholy.

2VE:


Základní pojmyOrientovaný a neorientovaný grafV orientovaném grafu jsou vždy orientované hrany, tj. hrany s definovaným počátečním a koncovým vrcholem.

V neorientovaných grafech se lze pohybovat přes hrany oběma směry.

Hrany i vrcholy jsou v četných aplikacích ohodnoceny Ohodnocený orientovaný Ohodnocený orientovaný

(neorientovaný) graf(neorientovaný) graf

),E,V(G


Základní pojmy

Sled:

Orientovaný

v1, e1, v2, e2, v3, e5, v4

Neorientovaný

v2, e3, v3, e5, v4, e6, v1

Není sledem

v1, e2, v3, e5, v2, e1, v4

Posloupnost vrcholů a hran jak jdou za sebou.

v 2

v 1

v 3

v 4

e 4e 1

e 2

e 3

e 5

e 6

v 2

v 1

v 3

v 4

e 4e 1

e 2

e 3

e 5

e 6


Základní pojmy

TahSled, kde se neopakují hrany

CestaSled, kde se neopakují vrcholy

Kořenový strom- orientovaný graf, kde existuje vrchol r (kořen), ze kterého jsou všechny vrcholy dostupné a nevede do něj žádná hrana.

r


Speciální pojmy

• Hamiltonovská cesta:

Cesta, která projde všemi vrcholy a každým pouze jedenkrát (turista).

• Eulerův tah:

Tah, který projde všemi hranami a každou pouze jedenkrát (sedm mostů v Königsbergu).


Popis grafu

• Incidenční maticí – orientace hran (+1, -1)

• Matice sousednosti – počet hran mezi sousedy

• Spojové seznamy – seznamy následníků

• Matice délek – délka hrany mezi vrcholy (i,j)

• Matice vzdáleností


Úlohy s grafy

Grafické znázornění úlohy je názorné a v jednoduchých případech lze odhalit řešení i bez použití jakéhokoliv algoritmu.Úloha pro převozníka:

Vlk, koza, zelí1) v, k, z, p2) 0

1) k, z2) v, p

1) v, z2) k, p

1) v, k2) z, p

1) k, z, p2) v

1) v, z, p2) k

1) v, k, p2) z

Nesmí nastat, nebudu kreslit

1) v2) k, z, p

1) k2) v, z, p

1) z2) v, k, p

1) k, p2) v, z

1) 02) v, k, z, p


Vlk, koza, zelí

1) v, k, z, p2) 0

1) v, z2) k, p

1) k, z, p2) v

1) v, z, p2) k

1) v, k, p2) z

1) v2) k, z, p

1) k2) v, z, p

1) z2) v, k, p

1) k, p2) v, z

1) 02) v, k, z, p


Vlk, koza, zelí

1) v, k, z, p2) 0

1) v, z2) k, p

1) k, z, p2) v

1) v, z, p2) k

1) v, k, p2) z

1) v2) k, z, p

1) k2) v, z, p

1) z2) v, k, p

1) k, p2) v, z

1) 02) v, k, z, p


Vlk, koza, zelí

1) v, k, z, p2) 0

1) v, z2) k, p

1) k, z, p2) v

1) v, z, p2) k

1) v, k, p2) z

1) v2) k, z, p

1) k2) v, z, p

1) z2) v, k, p

1) k, p2) v, z

1) 02) v, k, z, p


Prohledávání grafů

Úkolem prohledávání je hledání cesty z daného výchozího vrcholu do jednotlivých vrcholů grafu. To může pomoci i při vytváření grafu pro danou úlohu.

Tři způsoby prohledávání:

1) Značkování vrcholů

2) Prohledávání do šířky

3) Prohledávání do hloubky


Značkování vrcholů

Vrcholům přiřazujeme značky, pokud vrchol značku má, pak do něj vede cesta z daného výchozího vrcholu => vyjadřuje možnost

Výsledek lze převézt na kořenový strom, pokud zaznamenáme každou použitou hranu a její počáteční a koncový vrchol.

U neorientovaných grafů má tato metoda malý význam (pouze u velmi složitých, kde není zřejmé propojení jednotlivých vrcholů částí grafu).











Vlastnosti:

• Odpovídá na otázku: „Je možné?“

• Jednoduchý algoritmus

• Malé časové nároky: max V(G) – 1

• Nelze jej použít při hledání cest s určitými vlastnostmi (nejkratší, nejdelší).


Prohledávání grafu do šířky

Algoritmus lze přirovnat ke štěpné reakci. Probíhá tak, že počátečnímu vrcholu označíme všechny následníky, pak označíme následníky následníků atd.

Metoda vede k nalezení nejkratší cesty, za předpokladu, že hrany mají stejnou hodnotu => nejmenší počet tahů.


Prohledávání do šířky

D

ABC

1 2 3 4

D

A

B

C

1 2 3 4



D

ABC

1 2 3 4

D

A

B

C

1 2 3 4



D

ABC

1 2 3 4

D

A

B

C

1 2 3 4



D

ABC

1 2 3 4

D

A

B

C

1 2 3 4



D

ABC

1 2 3 4

D

A

B

C

1 2 3 4


Prohledávání grafu do šířky

Vlastnosti:

• Podobné časové nároky jako v případě značkování vrcholů: max V(G) – 1

• Získáme kořenový strom s nejmenším počtem úrovní


Prohledávání do hloubkyPodobá se průzkumu neznámých tras. Je základem pro další metody. Jdeme do hloubky grafu kam až můžeme a pak se vracíme a hledáme odbočky, kterými lze dále pokračovat.

Algoritmus je časově náročnější než oba předešlé, avšak jeho úpravou a zaznamenáváním jednotlivých tras jej lze využít pro hledání cest splňujících nějakou speciální podmínku. Například cesta začínající v r a obsahující všechny vrcholy =Hamiltonovská cesta


Návštěvník zábavního parku

• Chce se dostat na všechny atrakce

• Atrakce jsou spojeny elektrickým vláčkem

• Žádné nádraží nechce navštívit dvakrát



• Naplánuje jednu trasu a kouká kam až dojde.

• Označí si koncový vrchol a vrchol, který mu zabránil v cestě.



• Vrací s e zpět, až k prvnímu vrcholu, kde může odbočit.

• Označí hranu, kterou se vrátil.

• Pokud narazí na další koncový bod, vrátí se až za nejbližší vrchol, který působí konec a začne hledat znovu








Eulerův tah

• Uzavřený:

Vrátíme se do stejného vrcholu

• Otevřený:

Skončíme v jiném vrcholu


Eulerův tahUzavřený:• Neorientovaný – vrcholy mají sudý stupeň• Orientovaný – počet vstupních hran je stejný jako

počet výstupních

Otevřený:• Neorientovaný – obsahuje právě dva vrcholy s

lichým stupněm• Orientovaný – stejně jako neor. + do jednoho

vrcholu musí hrana vcházet, z druhého vycházet.


Eulerův tah

Musí se začít ve spodních vrcholech!

Oblíbená hvězda, kterou nelze nakreslit jedním tahem.

Sedm mostů v Königsbergu


Nejkratší cesty

Úloha: najít nejkratší cestu• z daného výchozího vrcholu do daného

cílového vrcholu• z daného výchozího vrcholu do každého vrcholu• z každého vrcholu do daného cílového vrcholu• mezi všemi uspořádanými dvojicemi

Lze vynechat smyčky a rovnoběžné hrany


Nejkratší cesty

Aby byla úloha řešitelná, nesmí graf obsahovat záporný cyklus. Pokud jej obsahuje, lze zkracovat vzdálenost do nekonečna.

Platí trojúhelníková nerovnost.


MATICE DÉLEK

Charakterizuje délky hran mezi jednotlivými vrcholy. Definice:

aii= 0,

aij= délka hrany mezi vrcholy i a j;

Pokud zde hrana nevede, pak značím nekonečno.


MATICE VZDÁLENOSTÍ

Charakterizuje vzdálenosti jednotlivých vrcholů. Definice:

uii= 0,

uij= vzdálenost mezi vrcholy i a j;

Pokud do vrcholu j nevede cesta z i pak je uij rovno nekonečnu.



Matice vzdáleností je přímo maticí nejkratších cest. Pokud nás nezajímá kudy cesta vede, lze použít k jejímu výpočtu následující způsoby:

1. Upravené násobení matic2. Floydův algoritmus



Floydův algoritmus:

)j,k(U)k,i(U)j,i(U)j,k(U)k,i(U)j,i(U

Podmínka:

ij

kj

ik



Příklad: Minimální náklady na dopravu zboží

12

45

3

11 Kè

6 Kè

5 Kè

4 Kè

3 Kè

7 Kè

8 Kè

3 Kè

2 Kè

0 86

7

111 2 3 4 5

12345

00

00

0

33

86

4 257

111 2 3 4 5

12345

00

00

33

4 25

0 86

7

111 2 3 4 5

12345

00

00

33

4 2518 15

0 86

7

111 2 3 4 5

12345

00

00

33

4 2518 15

14



Příklad: Minimální náklady na dopravu zboží

12

45

3

11 Kè

6 Kè

5 Kè

4 Kè

3 Kè

7 Kè

8 Kè

3 Kè

2 Kè

0 86

7

111 2 3 4 5

12345

00

00

33

4 2518 8

14 0 86

7

111 2 3 4 5

12345

00

00

33

4 2518 8

10

7 5

0 86

7

111 2 3 4 5

12345

00

00

33

4 2518 8

10

7 510129

8

7

11

Souèty35 Kè32 Kè27 Kè22 Kè38 Kè


Konstrukce nejkratších cest• Není vždy žádoucí určovat celou matici (paměť

počítače), chceme jen řádek týkající se našeho výchozího bodu.

• Chceme vědět, kudy nejkratší cesta vede.

Možnosti:• Ve Floydově algoritmu přibude matice Q(i,j),

informující o vrcholu těsně následujícím za vrcholem i při cestě z i do j.

• Algoritmus s opakovanou kontrolou všech hran


Opakovaná kontrola všech hran

Podmínka:

)e(Pv))e(Kv(Odkud

)e(a))e(Pv(U))e(Kv(U))e(Kv(U)e(a))e(Pv(U

Výpočet končí, pokud po průchodu všemi hranami nedošlo k žádné změně U.

Zápis provádíme nejlépe formou tabulky, kde každému Kv(e) náleží dva sloupce:

U(Kv(e)), odkud(Kv(e))


Kritická cesta

Příklad:

Chceme najít nejdelší cestu z vrcholu 0 do vrcholu 5. Cesta s nejdelšími časovými nároky

6

4 8 7

95

7

-6

-4 -8 -7

-9-5

-7

3 4

1 2 50

1 2 50

3 4


Hledání kritické cesty

1 2 3 4 5hrana

0U od. U od. U od. U od. U od.

a 0-6

krok 0

bcdef

- - - ------

0-6 - 0 - --40-6 3 0 - --4-120-6 1 0 - --4-150-6 1 0 1 --4-15 -13

g0-6 1 0 1 -20-4-15 -13 40-6 1 0 1 -20-4-15 -13 4

-6

-4 -8 -7

-9-5

-7

1 2 50

3 4

b

a

c e

dg

f3 4

1 2 50


Hledání kritické cesty

-6

-4 -8 -7

-9-5

-7

1 2 50

3 4

b

a

c e

dg

f3 4

1 2 50

1 2 3 4 5hrana U od. U od. U od. U od. U od.

a

krok 1

bcdefg 0-6 1 0 1 -20-4-15 -13 4

0-6 1 0 1 -20-4-15 -13 40-6 1 0 1 -20-4-15 -13 40-6 1 0 1 -20-4-15 -13 40-6 1 0 1 -20-4-15 -13 40-6 1 0 1 -20-4-15 -13 40-6 1 0 1 -20-4-15 -13 4


Závěrem

• Použití grafů je názornou pomůckou při řešení složitých problémů.

• Složitá řešení se zpravidla již neobejdou bez použití výpočetní techniky.

• Byl to jen letmý úvod, grafy se dále zabývají toky, hledání cyklů, nejlevnějších tahů, úlohami o párování…

Děkuji za pozornost


Zdroje

Demel Jiří, GRAFY a jejich aplikace, Academia, Praha 2002

Šeda Miloš, Teorie grafů, skripta VUT Brno, Brno 2003

Date post:	15-Jan-2016
Category:	Documents
Upload:	yen
View:	57 times
Download:	1 times

Základní teorie grafů a její aplikace

Documents