Kyonig teoremasi

Kirish

Ushbu bobda biz graf nazariyasidagi Kyonig teoremasini ko‘rib chiqamiz va u masalalarni yechishda bizga qanday yordam berishi mumkinligini ko‘ramiz.

Kyonig teoremasining bayoni

Graf nazariyasida juftlash nima ekanini hammamiz bilamiz. Yana bir tushunchani ko‘rib chiqamiz — cho‘qqilar qoplamasi (xususan, minimal cho‘qqilar qoplamasi).

Cho‘qqilar qoplamasi

$G$ grafidagi cho‘qqilar qoplamasi — bu cho‘qqilar to‘plamining qism to‘plami

S \subseteq V

shundayki, har bir $e \in E$ qirra $S$ dan kamida bitta cho‘qqiga insident bo‘ladi
(ya’ni qirra qoplangan).

Minimal cho‘qqilar qoplamasi — o‘lchami minimal bo‘lgan cho‘qqilar qoplamasi.

Kyonig teoremasi

Kirish