| 1.1.1-lemma. Ixtiyoriy orientirlanmagan grafda barcha uchlar darajalari yig’indisi qirralar sonining ikki baravariga teng.
Agar grafning uchlar to’plamini o’zaro kesishmaydigan shunday qisim to’plamlarga ajratish mumkin bo’lib, grafning ixtiyoriy qirrasi bu to’plamlarning biridan olingan qandaydir uchni ikkinchi to’plamdan olingan biron uch bilan tutashtiradigan bo’lsa, u holda bunday grafga ikki bo’lakli graf deyiladi. Agar ikki bo’lakli grafning turlibo’laklariga tegishli istalgan ikki uch qo’shni bo’lsa, u holda bugraf to’la ikki bo’lakli graf deyiladi.
To’la ikki bo’lakli grafni bilan belgilaymiz, bu yerda va bilan grafning bo’laklaridagi uchlar sonini belgilaymiz.graf uchun bo’lishi ravshan, bu yerda grafning uchlari soni, uning qirralari soni. Ikkinchidan katta ixtiyoriy natural soni uchun bo’lakli graf tushunchasini ham shunga o’xshash kiritish mumkin.
|
