• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Graf półeulerowski

    Przeczytaj także...
    Teoria grafów to dział matematyki i informatyki zajmujący się badaniem własności grafów. Informatyka rozwija także algorytmy wyznaczające pewne właściwości grafów. Algorytmy te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór nie związanych z grafami.Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.
    Łańcuch Eulera (droga Eulera, ścieżka Eulera, szlak Eulera) to taka ścieżka w grafie, która przechodzi przez każdą jego krawędź dokładnie raz. Jeżeli w danym grafie możliwe jest utworzenie takiej drogi, to jest on nazywany grafem półeulerowskim.

    Graf półeulerowski (graf semieulerowski) – graf rozważany w teorii grafów. Graf półeulerowski zawiera w sobie ścieżkę, która pozwala przejść przez wszystkie jego krawędzie tylko raz. Ścieżka ta nazywana jest ścieżką Eulera.

    Cykl Eulera to taki cykl w grafie, który przechodzi przez każdą jego krawędź dokładnie raz. Jeżeli w danym grafie możliwe jest utworzenie takiego cyklu, to jest on nazywany grafem eulerowskim.Leonhard Euler (ur. 15 kwietnia 1707 w Bazylei, zm. 18 września 1783 w Petersburgu) – szwajcarski matematyk i fizyk; był pionierem w wielu obszarach obu tych nauk. Większą część życia spędził w Rosji i Prusach. Jest uważany za jednego z najbardziej produktywnych matematyków w historii.
    Graf półeulerowski

    Graf eulerowski[]

     Osobny artykuł: Graf eulerowski.

    Jeżeli ścieżka Eulera jest zamknięta, to nazywana jest cyklem Eulera. Graf zawierający taki cykl nazywany jest eulerowskim. Nazwa pochodzi od nazwiska szwajcarskiego matematyka Leonharda Eulera, który jako pierwszy, zajmował się problematyką związaną z drogami w grafach.

    Krawędź grafu jest to para (zbiór dwuelementowy) wyróżnionych wierzchołków grafu, czyli takich, które są ze sobą połączone (sąsiednie). W reprezentacji graficznej jest to linia łącząca te wierzchołki. W szczególności krawędź może łączyć dwa te same wierzchołki i jest wówczas nazywana pętlą. Krawędź skierowaną, czyli będącą parą uporządkowanych wierzchołków, nazywamy łukiem.



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.007 sek.