Moje definice říká
A clique je graf, který má hranu spojující každou dvojici vrcholů
, ale jak chápu, hrana spojuje pouze dva vrcholy. Stejně jako $ A-B $ .
Pokud chceme spojit tři vrcholy, potřebujeme alespoň dva okraje. Například $ ABC $ .
Nechápu, jak hrana může spojit každý pár vrcholů.
Komentáře
- Není to ' jeden okraj $ e $, který spojuje všechny páry. Pro každý pár $ u, v \ ve V $ je hrana $ e_ {uv} $, která spojuje dva uzly. To znamená, že klika je (pod) graf, který obsahuje všechny možné hrany.
Odpověď
Připomínáme, že klika je podmnožinou $ C $ vrcholů neorientovaného grafu tak, že podgraf indukovaný $ C $ je plně propojen. To znamená, že každé dva odlišné vrcholy v $ C $ jsou spojeny odlišnou hranou grafu. To znamená různé hrany, ne stejné.
Takže na klika $ C $ obsahující $ k $ vertices $ v_1, v_2, .., v_k $ , existuje $ \ frac {k (k-1) } 2 $ hrany, které je spojují, to je počet možných neuspořádaných párů na prvcích $ k $ .
Příklad
Jak vidíte v předchozím obrázek, toto je klika na čtyřech vrcholech $ \ {{1,2,3,4} \} $ , takže každou hranu spojuje jiná hrana (tj. $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Můžete je spočítat a zjistit, že existují přesně $ 6 = \ frac {4 \ times 3} {2} $ hrany.
Komentáře
- Jak víte, že existují k (k-1) / 2 hrany?
- Pro každé 2 vrcholy existuje hrana. Kolik párů vrcholů máte od $ n $? $ \ binom {n} {2} $