Wyniki wyszukiwania dla: GRAF PLANARNY

• A note on compact and compact circular edge-colorings of graphs

  Publikacja

  • D. Dereniowski
  • A. Nadolski

  - DISCRETE MATHEMATICS - Rok 2008

  W pracy rozważamy dwa warianty kolorowania krawędzi grafów prostych i ważonych, mianowicie kolorowania zwarte oraz zwarte cyrkularne. Rozważamy relacje pomiędzy nimi. Dowodzimy, że każdy zewnętrznie planarny graf dwudzielny posiada zwarte pokolorowanie krawędziowe oraz, że problem ten dla grafów ogólnych jest NP-zupełny. Podajemy również wielomianowy 1.5-przybliżony algorytm oraz pseudowielomianowy dokładny algorytm zwartego cyrkularnego...

  Pełny tekst do pobrania w serwisie zewnętrznym

• Cztery algorytmy, które wstrząsnęły światem. Część III: Sprzęt czy oprogramowanie

  Publikacja

  • M. Kubale

  - Pismo PG - Rok 2019

  W ostatniej części tryptyku poruszamy problem przyjaznego rysowania grafów oraz prezentujemy algorytmy dla szybkiego mnożenia macierzy. Nasze rozważania kończymy ilustracją postępu w dziedzinie sprzętu i oprogramowania

• Planarność i zewnętrzna planarność grafów

  Publikacja

  • M. Dettlaff
  • D. Kuziak

  - Rok 2009

  Niech G będzie niepustym grafem prostym. Graf, który można przedstawić na płaszczyźnie w taki sposób, że żadne dwie krawędzie nie przecinają się nazywamy grafem płaskim, natomiast graf nazywamy planarnym, gdy jest on izomorficzny do grafu płaskiego. Jeśli dodatkowo wszystkie jego wierzchołki leżą na obszarze zewnętrznym, graf nazywamy zewnętrznie planarnym. Indeksem krawędziowym grafu G nazywamy najmniejsze k takie, że k-ty iterowany...