Graf planarny
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Graf planarny – graf, który można narysować na płaszczyźnie 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.
[edytuj] Kryterium Kuratowskiego
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.
[edytuj] Wzór Eulera
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 ze wzorem Eulera, jeżeli G jest grafem spójnym i planarnym, to | V | + | S | − | E | = 2, gdzie V - zbiór wierzchołków, E - zbiór krawędzi, S - zbiór ścian dowolnego rysunku płaskiego grafu G.
Wnioski ze wzoru Eulera:
- Jeżeli G jest planarny, 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.
| Olsztyn: 16-latka śmiertelnie zatruła się czadem |
|
Szesnastoletnia dziewczyna śmiertelnie zatruła się czadem. Dwie osoby, które były z nią w mieszkaniu nie ucierpiały - poinformowała Małgorzata Szmidt-Jeżewska, rzecznik prasowa warmińsko-mazurskiej straży pożarnej.
|
| Izrael ma nadzieję na owocne rozmowy z Egiptem |
|
Izrael wyraził nadzieję, że rozmowy z Egiptem na temat sytuacji w Strefie Gazy stworzą warunki, które pozwolą Izraelowi "zakończyć operację militarną".
|
| Irak wzywa do odwetu za Strefę Gazy |
|
Radykalny duchowny Muktada as-Sadr wezwał iracki ruch oporu do przeprowadzenia "operacji odwetowych" przeciwko siłom amerykańskim w Iraku, aby zaprotestować w ten sposób przeciw izraelskiej ofensywie w Strefie Gazy.
|
| Tragiczny bilans wojny w Strefie Gazy |
|
Co najmniej 702 Palestyńczyków zginęło, a 3100 zostało rannych podczas izraelskiej ofensywy w Strefie Gazy - podał szef służb ratowniczych.
|
| Posłowie za rozszerzeniem uprawnień "speckomisji" |
|
Za umożliwieniem sejmowej "speckomisji" dostępu do dokumentów i materiałów uzyskanych przez służby specjalne opowiedzieli się w środę, podczas debaty w Sejmie nad projektem zmian w regulaminie izby, posłowie ze wszystkich klubów parlamentarnych.
|