Теория графов и комбинаторика

ли в этой вершине, прежде чем перейти s другую вершину. Эйлеров цикл - это замкнутый мар1врут, оодэргадщий воа р а б р 9 , причем каждое и з них только один раз. Если ^абованиа Зс. ,~ К!1утооти н е осЗяаательно, то встает вопрос о(5 эйлеровой цепи. Таотрбма 10. Связдай граф & содержит эйлерову цепь эгда Мтолько то г да , когда ровно две его вершины амеют нечетные оте- лени, причем эйлерова цепь соединяет эти вервинн о нечетными отепеняш. Доказательство Цуоть - овяаный граф; ,1е^- вершины о В». 10ТНШЛИ отепеняш. Добавим новое ребро а; = (гг, и)-} . В гра­ фе (?+ос в о е вершины четны. Построим эйлеров цикл в &+за и за­ тем удалим и з него ребро сс Получим ейлерову (.iT-%^) - цепь в графе 9 . Обобщением теоремы 10.2 являетоя следуицая Теорема 10 . 3 . Т^уоть G - овязшй граф, имеющий Д<к вершш о нечетной отепеныо. Тогда граф можно предотавать как обьедине- НШ0 К реберно-непересекающихоя цепей. Эти цени соединяют пары вериин о нечетными отепенями. Аналогичные теоремы справедливы и для орграфов. Например, необходимым и доотчточиык! уоловием сущее вовання контура, со­ держащего вое дуги-и каждую аэ них только один т, яв.пявтоя условие.: V V ci'~(.vr) -'J~Cir). Si0.2. Гамильтоновы гпаФы Пуоть (? =( V , X ) - связный граф (мультйграф, псевдограф). Гамильтоповой цепью в 6 называется простая цепь, оодаркащая вое вершины графа. Гамильтоновнм циклом нааываетоя простой цикл.со - дерокащий все вершны графа. Граф (? пазнваетоя гамил;>10НйЁим, ОЛИ содержит гамильтонов цикл. Несмотря на кажущееся оходотво понятий эйларовнх и гамиль^оновых графов, аоцросы, относящиеся к с, щеотвсвани» и отысканию гамильтоиовйх Циклов, оказываются намного, больй сложными, . В наотоящее время на оущаотвует эффек- . тйвш"- общих опооо<<ов pemeHtH вопросов сущеотаованая и отыока- ' ния гашльтоновых циклов. Заметим,- что та« -как мы раооматриваем конечные графа, то любая -проблема "алгоритмически разрешима и решается алгорпыом полного яерабора. Однако в большинства практичеоких случаев ал­ горитм •ис.лот'о nepiadopa OKaaHBaeDOff физически явоущвотвенннм в оилу ог1й ¥ йичвинооти вовмокноотей вычиолителя. 63