Hledej
Zobraz:
Univerzity
Kategorie
Rozšířené vyhledávání
12 662
projektů
Teorie z předmětu Teorie grafů a její aplikace v dopravě
«»
| Přípona .doc |
Typ poznámky |
Stažené 2 x |
| Velikost 0,1 MB |
Jazyk český |
ID projektu 6928 |
| Poslední úprava 09.11.2015 |
Zobrazeno 1 940 x |
Autor: blackmagic |
Sdílej na Facebooku |
||
| Detaily projektu | ||
- Cena:
2 Kreditů - kvalita:
88,2% -
Stáhni
- Přidej na srovnání
- Univerzita:České vysoké učení technické v Praze
- Fakulta:Fakulta dopravní
- Kategorie:Technika » Doprava a spoje
- Předmět:Teorie grafů a její aplikace v dopravě
- Studijní obor:-
- Ročník:3. ročník
- Formát:MS Office Word (.doc)
- Rozsah A4:7 stran
1. Definice základních pojmů (graf, vrchol, hrana, stupeň vrcholu, incidence)
• Neorientovaný graf - uspořádaná trojice G = (V,X,p) {Vrcholy, X hrany, p incidence}
• Incidence - Přiřazení množiny hran na množinu všech neuspořádaných dvojic V
• Stupeň vrcholu - Počet hran incidujících s vrcholem
• Multigraf - připouští existenci násobných hran.
• Prostý graf - Nepřipouští existenci násobných hran
• Obyčejný - Nepřipouští existenci násobných hran a smyček
• Triviální - Pouze 1 V
• Prázdný - V = ; X =
• Diskrétní - Množina hran je
• Kompletní - Mezi každou dvojicí V X
• Acyklický graf - Takový, který neobsahuje jako svůj podgraf kružnici.
• Pravidelný graf - k-tého stupně, Pokud jeho všechny vrcholy mají stupeň k
• Vrcholově/Hranově ohodnocený - jestliže existuje funkce o(v)/o(h) která přiřadí každému vrcholu/hraně kladné číslo...
2. Podgrafy, různé typy podgrafů
• Pod(nad)grafem - G=(V,X,p) rozumíme: `G=(`V,`X,`p) pro kt.: `VV, `XX a pro hranu h`X platí `p(h)=p(h)
• Indukované podgrafy - množinou hran nebo vrcholů, nebo vypuštěním množiny hran a vrcholů
• Neorientovaný graf - uspořádaná trojice G = (V,X,p) {Vrcholy, X hrany, p incidence}
• Incidence - Přiřazení množiny hran na množinu všech neuspořádaných dvojic V
• Stupeň vrcholu - Počet hran incidujících s vrcholem
• Multigraf - připouští existenci násobných hran.
• Prostý graf - Nepřipouští existenci násobných hran
• Obyčejný - Nepřipouští existenci násobných hran a smyček
• Triviální - Pouze 1 V
• Prázdný - V = ; X =
• Diskrétní - Množina hran je
• Kompletní - Mezi každou dvojicí V X
• Acyklický graf - Takový, který neobsahuje jako svůj podgraf kružnici.
• Pravidelný graf - k-tého stupně, Pokud jeho všechny vrcholy mají stupeň k
• Vrcholově/Hranově ohodnocený - jestliže existuje funkce o(v)/o(h) která přiřadí každému vrcholu/hraně kladné číslo...
2. Podgrafy, různé typy podgrafů
• Pod(nad)grafem - G=(V,X,p) rozumíme: `G=(`V,`X,`p) pro kt.: `VV, `XX a pro hranu h`X platí `p(h)=p(h)
• Indukované podgrafy - množinou hran nebo vrcholů, nebo vypuštěním množiny hran a vrcholů
Klíčová slova:
teorie grafů
podgrafy
definice
komplementární grafy
algoritmus
PERT
dopravní sítě
excentricita
Obsah:
- 1. Definice základních pojmů (graf, vrchol, hrana, stupeň vrcholu, incidence)
2. Podgrafy, různé typy podgrafů
3. Faktorový podgraf, komplementární grafy
4. Komplementární grafy, autokomplementární grafy
5. Izomorismus
6. Matice na grafech (incidence, sousednosti, přilehlosti, přímých vzdáleností)
7. Způsoby prezentace grafů(výčet, matice, graf, množina)
8. Sled, tah, cesta
9. Theseova metoda
10. Souvislost grafů, číslo vrcholové, hranové souvislosti grafů
11. Orientované grafy, matice předchůdců, matice následovníků, matice incidence
12. Délka cesty, vzdálenost vrcholů
13. Dijkstrův algoritmus
14. Floydův algoritmus
15. Spolehlivost cesty, nejspolehlivější cesta, algoritmus
16. Kapacita cesty, cesta s maximální kapacitou, algoritmus
17. Maximální dráha, algoritmus
18. CPM - metoda kritické cesty
19. PERT
20. Dopravní síť- definice, tok na síti a jeho vlastnosti
21. Typy dopravních sítí
22. Ford-Fulkersonův algoritmus pro rovinné sítě
23. Ford-Fulkersonův algoritmus pro obecné sítě, značkovací metoda
24. Ford-Fulkersonův algoritmus pro intervalově ohodnocené sítě, přípustný tok
25. Aplikace úloh o tocích na dopravních sítích, neadresné toky, přiřazovací problém
26. Lokační úlohy, atrakční obvody-definice, vlastnosti
27. Vážená excentricita vrcholu/bodu, vzdálenostně optimální depo, absolutní depo
28. Hakimiho věta, Hakimiho algoritmus
29. Kritéria pro řešení lokačních úloh
30. Iterativní algoritmus
31. Stromy, vlastnosti, typy stromů, excentricita, radius, diametr, centrum, centroid
32. Konstrukční úlohy na grafech, kostra grafu
33. Eulerovský graf, Eulerovský tah
34. Hamiltonovský graf, Hamiltonovská kružnice, podmínky existence hamilt. kružnice
35. Fleuryho algoritmus, Edmondsův algoritmus
36. Heuristický algoritmus vyhledávání hamiltonovské kružnice v kompletním grafu
37. Metoda Branch & Bound, Littlův algoritmus, formulace úlohy obchodního cestujícího
38. Aplikace úlohy obchodního cestujícího, přiřazovací problém
39. Rovinné grafy, Kuratowského věta
40. Petersonův graf, homeomorfismus
41. Barvení grafu, chromatické číslo grafu, odhady chromatického čísla
42. Heuristický algoritmus barvení grafu, hypotéza 5/4 barev
43. Aplikace rovinných grafů