Liczba krawędzi w grafie dwudzielnym
: 19 cze 2017, o 17:25
Dany jest graf posiadający 7 wierzchołków:
a) jaka jest maksymalna liczba krawędzi w tym grafie, jeśli jest on dwudzielny?
b) jaka jest maksymalna liczba krawędzi w tym grafie, jeśli jest on trójdzielny?
W a) rozważam grafy dwudzielny pełne - istnieją następujące grafy:
\(\displaystyle{ K_{16} = 1 \cdot 6 = 6}\) krawędzi,
\(\displaystyle{ K_{25} = 2 \cdot 5 = 10}\) krawędzi,
\(\displaystyle{ K_{34} = 3 \cdot 4 = 12}\) krawędzi.
Więc maksymalna liczba krawędzi wynosi 12.
A jak w przykładzie b) ?
a) jaka jest maksymalna liczba krawędzi w tym grafie, jeśli jest on dwudzielny?
b) jaka jest maksymalna liczba krawędzi w tym grafie, jeśli jest on trójdzielny?
W a) rozważam grafy dwudzielny pełne - istnieją następujące grafy:
\(\displaystyle{ K_{16} = 1 \cdot 6 = 6}\) krawędzi,
\(\displaystyle{ K_{25} = 2 \cdot 5 = 10}\) krawędzi,
\(\displaystyle{ K_{34} = 3 \cdot 4 = 12}\) krawędzi.
Więc maksymalna liczba krawędzi wynosi 12.
A jak w przykładzie b) ?