Graf prosty

Graf prosty – graf bez pętli własnych i krawędzi wielokrotnych. Często określenie graf (bez przymiotników) oznacza graf prosty. Graf pełny K3 Graf dwudzielny...

„ G {\displaystyle G} jest grafem” oznacza w domyśle, że G {\displaystyle G} jest grafem prostym, graf przedziałowy – graf, utworzony ze zbioru odcinków...

Graf pełny – graf prosty, nieskierowany, w którym dla każdej pary węzłów istnieje krawędź je łącząca. Graf pełny o n {\displaystyle n} wierzchołkach oznacza...

sposobem – acykliczność, czyli brak możliwości chodzenia „w kółko”. Graf prosty G jest drzewem jedynie wtedy, gdy spełnia jeden z warunków: dowolne dwa...

elementem teorii grafów oraz wielu algorytmów. osiągalność (teoria grafów) droga (teoria grafów) cykl (teoria grafów) graf skierowany graf prosty Reinhard Diestel:...

Cykl prosty to droga zamknięta, czyli taka, której koniec (ostatni wierzchołek) jest identyczny z początkiem (pierwszym wierzchołkiem). Cykl prosty jest...

Pętla (pętla własna) – krawędź łącząca wierzchołek z nim samym. graf prosty teoria grafów ścieżka (teoria grafów) cykl (teoria grafów) p d e Teoria grafów...

Georgievicha Vizinga, który opublikował je w 1964 roku. Każdy nieskierowany graf prosty G można pokolorować krawędziowo używając liczby kolorów równej maksymalnemu...

Dany jest graf prosty G {\displaystyle G} o n {\displaystyle n} wierzchołkach ( v 1 , v 2 , … , v n ) {\displaystyle (v_{1},v_{2},\dots ,v_{n})} i m {\displaystyle...

Kutna. Problem ten jest NP-trudny. W wersji decyzyjnej problemu, danymi są graf i pewna liczba n, należy odpowiedzieć czy istnieje trasa komiwojażera krótsza...