Nr 01 · Słownik · Teoria informatyki · Matematyka dyskretna i teoria obliczeń

Teoria grafow kombinatoryka

16 pojęć w 10 podgrupach, z prostymi definicjami i źródłami.

Drzewa · 2

  • 01drzewoSpójny graf nieskierowany bez cykli; między każdą parą wierzchołków istnieje dokładnie jedna ścieżka.
  • 02minimalne drzewo rozpinająceMSTDrzewo zawierające wszystkie wierzchołki grafu ważonego i mające najmniejszą możliwą sumę wag krawędzi.

Kolorowanie · 2

  • 01kolorowanie grafuPrzypisanie etykiet (kolorów) wierzchołkom tak, by sąsiednie wierzchołki miały różne kolory, zwykle przy minimalnej liczbie kolorów.
  • 02liczba chromatycznaNajmniejsza liczba kolorów potrzebna do poprawnego pokolorowania wierzchołków grafu tak, by sąsiednie miały różne kolory.

Kombinatoryka przeliczeniowa · 1

  • 01współczynnik dwumianowyLiczba sposobów wyboru k-elementowego podzbioru ze zbioru n-elementowego, oznaczana C(n,k); podstawowa wielkość kombinatoryki przeliczeniowej.

Marszruty i cykle · 2

  • 01cyklZamknięta marszruta o co najmniej trzech wierzchołkach, w której wierzchołek początkowy pokrywa się z końcowym, a pozostałe się nie powtarzają.
  • 02ścieżkaCiąg wierzchołków połączonych krawędziami, w którym żaden wierzchołek nie powtarza się; łączy wierzchołek początkowy z końcowym.

Obwody specjalne · 1

  • 01cykl EuleraZamknięta marszruta przechodząca przez każdą krawędź grafu dokładnie raz; istnieje wtedy, gdy graf jest spójny i wszystkie stopnie są parzyste.

Parametry grafu · 1

  • 01stopień wierzchołkaLiczba krawędzi incydentnych z danym wierzchołkiem; w grafie skierowanym rozróżnia się stopień wejściowy i wyjściowy.

Planarnosc · 1

  • 01graf planarnyGraf, który można narysować na płaszczyźnie tak, że jego krawędzie przecinają się wyłącznie we wspólnych wierzchołkach.

Rodzaje grafow · 3

  • 01DAGdirected acyclic graphSkierowany graf acykliczny (directed acyclic graph) — digraf bez cykli skierowanych; dopuszcza sortowanie topologiczne wierzchołków.
  • 02graf dwudzielnyGraf, którego wierzchołki dzielą się na dwa rozłączne zbiory tak, że każda krawędź łączy wierzchołek z jednego zbioru z wierzchołkiem z drugiego.
  • 03graf skierowanydigrafGraf, w którym krawędzie (łuki) mają ustaloną orientację — są uporządkowanymi parami wierzchołków wskazującymi kierunek relacji.

Skojarzenia i przeplywy · 2

  • 01przepływ w sieciFunkcja przypisująca łukom sieci wartości spełniające ograniczenia przepustowości i zachowania przepływu w wierzchołkach pośrednich.
  • 02skojarzenieZbiór krawędzi grafu, z których żadne dwie nie mają wspólnego wierzchołka; skojarzenie maksymalne ma największą liczność.

Spojnosc · 1

  • 01spójność grafuWłasność grafu polegająca na istnieniu ścieżki między każdą parą wierzchołków; w grafach skierowanych rozróżnia się spójność silną i słabą.

Pozostałe grupy — Matematyka dyskretna i teoria obliczeń

Grupa pojęć · Matematyka dyskretna i teoria obliczeń16 haseł