Эйлер графы

Эйлер графы — Эйлер циклы бар графтар. G=(V, Х) графы берілсін. G графының барлық төбелері мен қабырғаларын қамтитын цикл Эйлерлік цикл деп аталады

Кёнигсберг көпірлері графы. Бұл эйлерлік граф емес, сондықтан шешімі жоқ.

Тарихы. Кенигсберг есебі.

Тарихы жағынан топология және графтар теориясы Л.Эйлердің Кенигсберг көпірлері туралы есепті шығаруынан бастап пайда болды. Бұл есеп 1736 жылы Петербург ғылым академиясының журналында жарияланған. Кенигсберг (қазір Калининград) қаласы Прегал өзенінің екі жағасында және өзен ішіндегі екі аралда орналасқан. Қала халқы оның бір бөлігінен екінші бөлігіне көпір арқылы өтеді. Аралдар және жағалар 7 көпірлермен қосылған (8-сурет). «Кенигсбергтің бір ауданындағы (құрылықтағы) үйінен шыққан адам әр көпірден бір-ақ рет өтіп, қаланы түгел аралап, шыққан үйіне қайта орала ма?» Кенигберг есебі.

Теорема 1. Егер графтың эйлерлік циклы болса, онда ол байланысқан граф болады және оның төбелерінің дәрежесі жұп сан болады. Дәлелдеу. Графтың байланысқан болатындығы оның эйлерлік граф екендігінен шығады. Эйлерлік цикл әрбір қабырғаны тек бір рет қана қамтитын болғандықтан, әр төбеге қарындаштың ұшы қанша рет барса сонша рет шығады. Сондықтан әр төбенің дәрежесі екі бірдей қосылғыштан тұрады: біреуі төбеге ену нәтижесі, екіншісі төбеден шығу нәтижесі. Ендеше, төбе дәрежесінің жұп болғаны. Осы теоремаға кері тұжырым да дұрыс болады. Теорема 2. Егер граф байланысқан және төбелерінің дәрежесі жұп болса, онда оның эйлерлік циклы болады.