Yashiklar prinsipi

Эйлер ва Гамилтон графлари

Режа:

1. 
   Эйлер графлари.
   
2. 
   Гамилтон графлари
   
3. 
   Дирак теоремаси.
   

Калит сўзлар: Граф, уч, қирра, цикл, эйлер занжири, эйлер цикли, эйлер графи, ярим эйлер графи, ориентирланган эйлер йўли, ориентирланган эйлер графи, Флёри алгоритми, Гамилтон занжири, Гамилтон цикли, Гамилтон графи, ярим Гамилтон графи, коммивояжер масаласи.

1. Эйлер графлари. Графлар назариясининг шаклланиши Кёнигсберг кўприклари ҳақидаги масала билан боғлиқ эканлиги яхши маълум. Л. Эйлер 1736 йилда бу масаланинг ечимга эга эмаслигини исботлади. У графлар назариясининг анча умумий ҳисобланган қуйидаги саволига ҳам жавоб топди: қандай шартлар бажарилганда боғламли графда барча қирралардан фақат бир марта ўтадиган цикл мавжуд бўлади?
Графнинг ҳар бир қиррасидан фақат бир марта ўтадиган занжир эйлер занжири деб аталади. Ёпиқ эйлер занжирига (жаъни эйлер циклига) эга граф эйлер графи деб аталади. Агар графда ёпиқ бўлмаган эйлер занжири топилса, у ҳолда бундай граф ярим эйлер графи деб аталади.
1- теорема. Боғламли граф эйлер графи бўлиши учун ундаги барча учларнинг даражалари жуфт бўлиши зарур ва етарлидир.