Kalkulator Krawędzi Grafu (Graf Pełny)

Wzór

How this is calculated

Graf pełny K_n łączy każdą parę różnych wierzchołków. Wpisz n — liczbę wierzchołków (liczba całkowita, n ≥ 0) — i wybierz typ grafu. W nieskierowanym grafie pełnym każda nieuporządkowana para {a, b} tworzy jedną krawędź, więc całkowita liczba krawędzi wynosi współczynnik dwumianowy C(n, 2) = n(n−1)/2 — klasyczna „liczba uścisków dłoni”, która mówi też, ile uścisków dłoni wymienią n osób, gdy każda raz uściśnie dłoń wszystkich pozostałych.

Skierowany (zorientowany) graf pełny zlicza natomiast każdą uporządkowaną parę (a, b) taką, że a ≠ b, dopuszczając strzałkę w każdym kierunku. Pierwszego wierzchołka można wybrać na n sposobów, a drugiego — na (n−1) sposobów, co daje n(n−1) krawędzi — dokładnie dwa razy więcej niż w wariancie nieskierowanym. Obie formuły rosną kwadratowo wraz z n, dlatego wykres liczby krawędzi w zależności od liczby wierzchołków wyraźnie się zakrzywia ku górze.

Kalkulator zaokrągla w dół każde wprowadzone ułamkowe n do liczby całkowitej i odrzuca wartości ujemne. Przypadki brzegowe działają naturalnie: n = 0 i n = 1 dają 0 krawędzi (nie ma żadnych par), a n = 2 daje 1 krawędź nieskierowaną lub 2 krawędzie skierowane. Pętle własne i multikrawędzie nie są zliczane, zgodnie z definicją prostego grafu pełnego.