3.6
Эйлердік графтар
Егер байланысты графтың оның барлық
доғаларынан өтетін жай циклы болса, онда бұл граф эйлердік граф деп аталады.
Теорема 1 Ақырлы байланысты граф эйлердік болуы үшін оның
барлық төбелерінің дәрежелері
жүп сандар болуы қажетті және жеткілікті.
Егер байланысты графтың оның барлық
доғаларынан өтетін жай тізбесі
болса, онда бұл граф квазиэйлердік
граф деп аталады.
Теорема 2 Ақырлы байланысты граф квазиэйлердік болуы
үшін оның барлық төбелерінің дәрежелері
жүп сандар немесе барлық төбелерінің дәрежелері
тек екеуінен басқа жүп сандар болуы қажетті және
жеткілікті.
Бірінші жағдайда эйлердік тізбе эйлердік цикл болады, ал екінші жағдайда эйлердік тізбе тақ
дәрежелі төбелерінің біреуінде басталып, екіншісінде
аяқталады.