Egy véges gráfban hány darab kör lehet? Csak 1 vagy lehet több is? Tudtok példát mondani amelyikben több van.

Ha nagyon sok kör kellene, akkor a teljaes gráfokat kell megnézni.

Itt látható, hogy a következő oldalszámú (balra) szabályos sokszögekben hány kör van (jobbra):

3 1

4 7

5 37

6 197

7 1172

8 8018

9 62814

10 556014

11 5488059

12 59740609

Talán majd jobban látszik:

3 .... 1

4 .... 7

5 .... 37

6 .... 197

7 .... 1172

8 .... 8018

9 .... 62814

10 ... 556014

11 ... 5488059

12 ... 59740609

Pl. a 4 szögpontú (ABCD) teljes gráfban

ABCD

ABDC

ACBD

ABC

ABD

ACD

BCD

Ez mind különböző körnek számít.

Rajzold le, akkor látszik.

Magyarázat a fenti számításokhoz.

Az n szögpontú teljes gráf összes k hosszúságú (3≤k≤n) köre:

C(n,k)*k!/k/2 darab.

(C(n,k): „n alatt a k”)

Ezeket kell összegezni k= 3,…,n -re

Kiválasztok n-ből k pontot → C(n,k) -féleképpen,

veszem az összes sorrendjét → *k!

kiszűröm a körbeforgásokat: → /k

kiszűröm a tükörképeket: → /2

Ezeket kell összegezni k=3,…,n -re, mert legalább 3 legfeljebb n hosszúságú lehet a kör.

(Ezekből a Hamilton-körök száma: k=n → (n-1)!/2)