Szybszy dostęp niż przeglądarce!
13 kontakty: Algorytm wielomianowy, Cykl (teoria grafów), Graf (matematyka), Graf dwudzielny, Graf krawędziowy, Graf przedziałowy, Klika (teoria grafów), Kolorowanie grafu, Liczba chromatyczna, Podgraf, Problem kliki, Problem P, Problem zbioru niezależnego.
Algorytm wielomianowy
Algorytm wielomianowy – algorytm, którego czas działania ograniczony jest przez wielomian od rozmiaru danych wejściowych.
Nowy!!: Graf doskonały i Algorytm wielomianowy · Zobacz więcej »
Cykl (teoria grafów)
Przykładowy graf cykliczny Cykl grafu – zamknięta droga prosta e_a,e_b,\dots,e_z, taka że krawędź e_z kończy się w początkowym wierzchołku drogi.
Nowy!!: Graf doskonały i Cykl (teoria grafów) · Zobacz więcej »
Graf (matematyka)
Graf – podstawowy obiekt rozważań teorii grafów, struktura matematyczna służąca do przedstawiania i badania relacji między obiektami.
Nowy!!: Graf doskonały i Graf (matematyka) · Zobacz więcej »
Graf dwudzielny
Przykładowy graf dwudzielny Pełny graf dwudzielny K_3,4 Graf dwudzielny – graf, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łącząwierzchołków tego samego zbioru.
Nowy!!: Graf doskonały i Graf dwudzielny · Zobacz więcej »
Graf krawędziowy
Graf i jego graf krawędziowy. Kolory pokazująprzejście krawędzi w wierzchołki Graf krawędziowy (ang. line graph) grafu G – taki graf F.
Nowy!!: Graf doskonały i Graf krawędziowy · Zobacz więcej »
Graf przedziałowy
Graf przedziałowy – graf utworzony ze zbioru odcinków na prostej, poprzez przypisanie każdemu odcinkowi wierzchołka i połączenie krawędziami wierzchołków, których odcinki się nakładają.
Nowy!!: Graf doskonały i Graf przedziałowy · Zobacz więcej »
Klika (teoria grafów)
Klika – podgraf, w którym każde dwa wierzchołki sąpołączone krawędzią.
Nowy!!: Graf doskonały i Klika (teoria grafów) · Zobacz więcej »
Kolorowanie grafu
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ł.
Nowy!!: Graf doskonały i Kolorowanie grafu · Zobacz więcej »
Liczba chromatyczna
Liczba chromatyczna – liczba kolorów niezbędna do optymalnego klasycznego (wierzchołkowego) pokolorowania grafu, czyli najmniejsza możliwa liczba k taka, że możliwe jest legalne pokolorowanie wierzchołków grafu G. Oznacza się jąsymbolem \chi(G).
Nowy!!: Graf doskonały i Liczba chromatyczna · Zobacz więcej »
Podgraf
Podgraf danego grafu G to graf powstały przez usunięcie z grafu G pewnej liczby wierzchołków lub krawędzi (z tym zastrzeżeniem, że usuwając pewien wierzchołek usuwamy wszystkie do niego przyległe krawędzie).
Nowy!!: Graf doskonały i Podgraf · Zobacz więcej »
Problem kliki
Problem kliki – jeden z pierwszych zidentyfikowanych problemów NP-zupełnych.
Nowy!!: Graf doskonały i Problem kliki · Zobacz więcej »
Problem P
Problem P (deterministycznie wielomianowy) – problem decyzyjny, dla którego rozwiązanie można znaleźć w czasie wielomianowym.
Nowy!!: Graf doskonały i Problem P · Zobacz więcej »
Problem zbioru niezależnego
Problem zbioru niezależnego – przykład problemu NP-zupełnego z teorii grafów.
Nowy!!: Graf doskonały i Problem zbioru niezależnego · Zobacz więcej »
