Na stronie używamy cookies. Korzystanie z witryny oznacza zgodę na ich wykorzystywanie. Szczegóły znajdziesz w Regulaminie.
ZAMKNIJ X

Teorii grafów – podstawy, właściwości, zastosowanie

Ostatnio komentowane
Witam Dla mnie jednym z największych paradoksów współczesnego świata jest fakt,że p...
pawlo0 • 2017-08-16 17:57:59
WIEM,ŻE MISJE POKOJOWE ŚĄ BARDZO NIEBEZPIECZNE.Podziwiam ludzi,którzy są na misji,ż...
tereska1 • 2017-08-15 08:19:23
Dobre zestawienie. Polecam także ten artykuł http://edueduonline.pl/blog/e-mail-angielsk...
Sara • 2017-08-09 10:30:02
Umiem w matme wiem ile to jest pienc pluz czy
Kujon • 2017-08-08 17:08:22
ale ktoś trafił jak kulą w płot z Jarosławem Mądrym
b • 2017-08-11 12:35:03
Autor:
Drukuj
Drukuj
Rozmiar
AAA

Teorii grafów – podstawy, właściwości, zastosowanie

Teoria grafów zawdzięcza swój początek mieszkańcom Królewca, którzy zastanawiali się w jaki sposób należy zaplanować trasę wieczornego spaceru tak, by po każdym z królewieckich mostów przejść tylko razy.

Problem został rozwiązany dopiero przez Leonarda Eulera, który posłużył się następującym rozumowaniem:

Każdy spójny fragment lądu oznaczmy jednym punktem, natomiast mosty łączące poszczególne fragmenty lądu oznaczane będą krawędziami łączącymi te punkty. W taki sposób utworzona „mapa” królewieckich mostów wygląda jak na poniższym rysunku.

 

Tym co zrobił Euler dalej, było sformułowanie podstaw teorii grafów - w tym pojęć takich jak krawędź, wierzchołek oraz stopień wierzchołka. Dla powyższego grafu każdy z wierzchołków jest nieparzystego stopnia (trzy wierzchołki są stopnia równego 3, jeden wierzchołek jest stopnia 5). I okazuje się, że to wystarcza do tego, by nie dało się zaplanować spaceru tak, jak planowali mieszkańcy miasta.

W języku teorii grafów graf o tej własności nazywany jest grafem nie-eulerowskim, natomiast graf, w którym da się „zaplanować spacer” przez wszystkie krawędzie, w tym każdą tylko raz - jest grafem eulerowskim a trasę taką (tj. ciąg kolejnych wierzchołków i krawędzi, przez które przechodzimy), nazywamy cyklem Eulera. 

Tak narodziła się teoria grafów - matematyczna idea, która stoi między innymi u podstaw dzisiejszej informatyki, a także wielu innych praktycznych zastosowań.

 

Ciekawym wynikiem jest także tzw. twierdzenie o uścisku dłoni - będące matematyczną kodyfikacją faktu, że niezależnie od tego, ile osób podaje sobie dłoń, każdy uścisk dłoni łączy parzystą ich liczbę. W teorii grafów to twierdzenie brzmi następująco: w każdym grafie liczba wierzchołków nieparzystego stopnia musi być parzysta.

Polecamy również:

Komentarze (0)
1 + 2 =