Search results for: GRAF PLANARNY

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

  Publication

  • D. Dereniowski
  • A. Nadolski

  - DISCRETE MATHEMATICS - Year 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...

  Full text to download in external service

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

  Publication

  • M. Dettlaff
  • D. Kuziak

  - Year 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...

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

  Publication

  • M. Kubale

  - Pismo PG - Year 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