• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Graf planarny

    Przeczytaj także...
    Stopień wierzchołka w grafie to liczba krawędzi sąsiadujących z wierzchołkiem. Jest on równy sumie liczb wszystkich łuków wchodzących, wychodzących, krawędzi i pętli; każdą pętlę liczy się jednak jak dwie krawędzie. W grafach skierowanych można też wyróżnić stopień wchodzący i stopień wychodzący. Są to odpowiednio liczby łuków wchodzących do i wychodzących z wierzchołka.Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru.
    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.

    Graf planarnygraf, który można narysować na płaszczyźnie (i każdej powierzchni genusu 0) tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim.

    Kazimierz Kuratowski (ur. 2 lutego 1896 w Warszawie, zm. 18 czerwca 1980 w Warszawie), polski matematyk, jeden z czołowych przedstawicieli warszawskiej szkoły matematycznej.Twierdzenie Kuratowskiego – twierdzenie teorii grafów sformułowane i udowodnione przez Kazimierza Kuratowskiego w 1930 roku.

    Kryterium | edytuj kod]

    Dwa minimalne grafy, które nie są planarne, to K5 i K3,3. Twierdzenie Kuratowskiego (1930) mówi, że graf skończony jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homeomorficznego z grafem K5 ani z grafem K3,3.

    Wzór Eulera, wzór Eulera dla grafów płaskich – twierdzenie teorii grafów opisujące zależność między liczbą wierzchołków, ścian i krawędzi grafu płaskiego.Genus - pojęcie występujące w topologii i topologii algebraicznej, niezmiennik topologiczny, liczba całkowita charakteryzująca rozmaitość topologiczną równa liczbie otworów w rozmaitości. Tak więc dla sfery jest to 0, dla torusa 1, dla precelka 3 itp.

    Complete graph K5.svg Complete bipartite graph K3,3.svg

    Twierdzenie | edytuj kod]

    Dowolny rysunek płaski grafu planarnego wyznacza spójne obszary płaszczyzny zwane ścianami. Dokładnie jeden z tych obszarów, zwany ścianą zewnętrzną, jest nieograniczony.

    Zgodnie z wzorem Eulera, jeżeli oraz jest grafem spójnym i planarnym, to gdzie – zbiór wierzchołków, – zbiór krawędzi, – zbiór ścian dowolnego rysunku płaskiego grafu

    Twierdzenie o czterech barwach – dla każdego skończonego grafu planarnego ( V , E ) {displaystyle left(V,E ight)} istnieje funkcja k : V → { k 1 , k 2 , k 3 , k 4 } {displaystyle k:,V ightarrow left{k_{1},k_{2},k_{3},k_{4} ight}} , taka że ∀ { v 1 , v 2 } ∈ E ( k ( v 1 ) ≠ k ( v 2 ) ) {displaystyle forall _{{v_{1},v_{2}}in E}left(k(v_{1}) eq k(v_{2}) ight)} , czyli możliwe jest przypisanie każdemu z jego wierzchołków jednej z czterech liczb 1, 2, 3 i 4 w taki sposób, aby żadne sąsiednie wierzchołki nie miały przyporządkowanej tej samej liczby. Jest to jeden z najsłynniejszych problemów matematycznych.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.

    Wnioski ze wzoru Eulera[ | edytuj kod]

  • Jeżeli G jest planarny i posiada składowych spójnych, to
  • Jeżeli G jest planarny i to
  • Jeżeli G jest planarny, to wierzchołek o najmniejszym stopniu jest stopnia co najwyżej 5.
  • Zgodnie z twierdzeniem o czterech barwach, graf planarny daje się zawsze pokolorować przy użyciu co najwyżej czterech kolorów.

    Graf płaski - przedstawienie grafu planarnego na płaszczyźnie w taki sposób, że żadne dwie krawędzie grafu się nie przecinają.

    Zobacz też[ | edytuj kod]

  • domki i studnie
  • Przypisy[ | edytuj kod]

    1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 67, 80. ISBN 0-387-95014-1.




    Reklama

    Czas generowania strony: 0.023 sek.