Толық граф

Уикипедия — ашық энциклопедиясынан алынған мәлімет
Мұнда ауысу: шарлау, іздеу

Толық граф — кез келген екі төбесі қабырғамен байланысқан қарапайым граф. Яғни, n төбелі толық графта n(n-1)/2 қабырғалары бар және бұндай граф K_n деп белгіленеді. Дәрежесі n-1 болатындай Жүйелі граф болып табылады.

K_1 ден K_4 ке дейін Планар граф болып табылады. Төбелер саны көп болатындай толық графтар планар бола алмайды, себебі олар K_5 ішкі графты қамтиды, сондықтан да Понтрягин-Куратовский теоремасы шарттарын қанағаттандырмайды.

Төменде төбелер саны 1ден 8ге дейін болатын толық графтар және олардың қабырғалар саны берілген.

K_1: 0 K_2: 1 K_3: 3 K_4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
K_5: 10 K_6: 15 K_7: 21 K_8: 28
Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg