To tylko jedna z 126 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Leonhard Euler (ur. 15 kwietnia 1707 r. w Bazylei - Szwajcaria, zm. 18 września
1783 r. w Petersburgu - Rosja) - szwajcarski matematyk, fizyk i astronom, jeden z
twórców nowoczesnej matematyki.
Problem ten został postawiony pierwszy raz w 1962 roku przez matematyka chi«ski
Mei-Ku Kwan.
Wiadomo, że listonosz doręczając pocztę musi przejeść przez wszystkie ulice danego
rejonu i powrócić na pocztę.
Jedno, ale nie jedyne, z możliwych rozwiązań jest pokazane na rysunku
wg którego naprawy oznaczone kolorem czerwonym będą realizowane pierwszego
dnia, drugiego dnia naprawy oznaczone kolorem niebieskim, a trzeciego - naprawa
oznaczona kolorem niebieskim.
Indeks chromatyczny dla powyższego grafu wynosi ¯(G) = 3, a zatem zgodnie z
założeniami nie ma możliwości zrealizowania całego zamówienia w czasie krótszym
niż trzy dni.
> >
(…)
…¡, która przechodzi przechodzi
przez wszystkie wierzchoªki grafu, przy czym przez ka»dy wierzchoªek oprócz
pierwszego i ostatniego dokªadnie jeden raz.
95 / 126
Problem komiwoja»era
Problem podania warunku koniecznego i dostatecznego na to, aby graf spójny G
miaª cykl Hamiltona postawiª po raz pierwszy matematyk irlandzki sir William
Hamilton (1805-1865) w 1859 roku.
96 / 126
Problem komiwoja»era
Problem podania warunku koniecznego i dostatecznego na to, aby graf spójny G
miaª cykl Hamiltona postawiª po raz pierwszy matematyk irlandzki sir William
Hamilton (1805-1865) w 1859 roku.
Dotychczas podano wiele warunków dostatecznych w grae spójnym, ale do dzi± nie
s¡ znane warunki konieczne pozwalaj¡ce stwierdzi¢ w przypadku ogólnym, »e dany
spójny graf G ma cykl Hamiltona.
97 / 126
Problem komiwoja»era
Problem podania warunku koniecznego i dostatecznego na to, aby graf spójny G
miaª cykl Hamiltona postawiª po raz pierwszy matematyk irlandzki sir William
Hamilton (1805-1865) w 1859 roku.
Dotychczas podano wiele warunków dostatecznych w grae spójnym, ale do dzi± nie
s¡ znane warunki konieczne pozwalaj¡ce stwierdzi¢ w przypadku ogólnym, »e dany
spójny graf G ma cykl Hamiltona.
Twierdzenie
Graf peªny, posiadaj¡cy…
… Teoria grafów i jej zastosowania.
1 / 126
Mosty królewieckie
W Królewcu, na rzece Pregole znajduj¡ si¦ dwie wyspy poª¡czone ze sob¡, a tak»e z
brzegami za pomoc¡ siedmiu mostów, tak jak pokazuje rysunek
2 / 126
Mosty królewieckie
W Królewcu, na rzece Pregole znajduj¡ si¦ dwie wyspy poª¡czone ze sob¡, a tak»e z
brzegami za pomoc¡ siedmiu mostów, tak jak pokazuje rysunek
3 / 126
Mosty królewieckie…
… / 126
Podstawowe denicje
Denicja
Stopniem wierzchoªka nazywamy ilo±¢ kraw¦dzi wychodz¡cych z tego wierzchoªka.
32 / 126
Cykl Eulera
Denicja
Cyklem Eulera nazywamy tak¡ zamkni¦t¡ drog¦ prost¡, która przechodzi przez
wszystkie kraw¦dzie grafu (oczywi±cie przez ka»d¡ tylko jeden raz).
33 / 126
Cykl Eulera
Denicja
Cyklem Eulera nazywamy tak¡ zamkni¦t¡ drog¦ prost¡, która przechodzi przez
wszystkie kraw…
... zobacz całą notatkę
Komentarze użytkowników (0)