4Основытеорииграфов

Граф–этоматематическоепонятие,котороеслужитдлямоделированиясвязеймеждуобъектами.Различаюториентированныеинеориентированныеграфы.Точныеопределе-нияданыниже.

4.1Основныепонятия

(Неориентированным)графомназываетсяпараконечныхмножеств(V,E),гдеV–произ-вольноемножествообъектов,называемыхвершинами,иE⊆{{i,j}|i,j∈V}–множествонеупорядоченныхпарвершин,где{i,j}∈Eназываетсяребром.

Ориентированнымграфом(орграфом)называетсяпараконечныхмножеств(V,A),гдеV

–множествовершин,иA⊆{(i,j)|i,j∈V}–множествоупорядоченныхпарвершин,где(i,j)∈Aназываетсядугой.

Мультиграфом(ориентированныммультиграфом)называетсяграфскратнымиребрами

(кратнымидугами).

Примеры:рисункиграфовс3вершинами.

Определения.Вершинаiявляетсяначальной,авершинаj–конечнойвершинойдуги(i,j).Приэтомiиj–смежныевершины,адуга(i,j)инцидентнавершинамiиj.Та-каяжетерминологияиспользуетсядлянеориентированныхграфов–смежныевершиныиинцидентныеребра.Дуга(i,j)выходитизiивходитвj.Если(i,j)–дуга,тоiназы-ваетсянепосредственнымпредшественникомj,аj–непосредственнымпоследователемi.Количестводуг,входящихввершинуiназываетсястепеньюзаходаэтойвершины,аколичестводуг,выходящихизвершиныiназываетсястепеньюисходаэтойвершины.В

^{неориентированномграфевершиныiиjназываютсяконцамиребра{i,j}.Количество}

ребер,инцидентныхвершинеi,называетсястепеньювершиныi.

МаршрутомвнеориентированномграфеG=(V,E)называетсятакаяпоследователь-ностьвершинW=(v₀,v₁,...,v_k),k≥0,что{v_i−1,v_i}∈E,i=1,...,k.Графназывается

связным,еслисуществуетмаршрут,связывающийлюбыеегодвевершины.Говорят,чтомаршрутWсвязываетвершиныv_0иv_k,авершиныv₁,...,v_{k−1являют}сявнутренними

^{вершинамиэтогомаршрута.Количествовершинмаршрутаназываетсяегодлиной.Марш-}

рутWназываетсязамкнутым,еслиk>0иv_k=v₀.Маршрутназываетсяцепью,есливнемнетповторяющихсявершин.Замкнутыймаршрут,вкоторомникакиевершины,кромепервойипоследней,неповторяются,называетсяциклом.

Аналогамиприведенныхвышеопределенийдляорграфовявляютсяследующие.

Граф	Маршрут	Цепь	Цикл
Орграф	Путь	Простойпуть	Цикл

Цикл,которыйвключаетвсевершиныграфа,называетсягамильтоновым.Граф,которыйсодержитгамильтоновцикл,называетсягамильтоновым.

Замкнутыймаршрут,которыйвключаеткаждоеребрографаровноодинраз,называетсяэйлеровыммаршрутом,аграф,которыйсодержиттакоймаршрут,называетсяэйлеровымграфом.Задачу,являетсялиграфэйлеровым,впервыепоставилирешилЭйлер.В1736г.онписал:”ВгородеКенигсбергеестьдваострова,которыесоединяютсямеждусобойи

сберегамирекисемьюмостами(см.Pис.3).

_❦b

_✟^✟✟

_✟^✟✟

^{❦a ❦c}

^❍❍_❍

^d

^❍❍_❍

^❦

Рис.3:Граф"Кенигсбергскиемосты".aиc-острова,bиd-берега.

Можнолиспланироватьпрогулкутак,чтобы,начинаясодногоиз4участковсушиa,b,c,d,

пройтипокаждомуизэтихмостоводинразивернутьсявначальныйпункт?

Теорема3(Эйлер,1736г)Связныймультиграфявляетсяэйлеровымтогдаитолькотогда,когдавсееговершиныимеютчетнуюстепень.

4.2 Алгоритмпостроенияэйлеровацикладлянеориентированно-гографа

Шаг0.Проверяем,являетсялиграфG=(V,E)связнымичетнылистепениеговершин.Еслиэтонетак,эйлеровацикланесуществует.

^{Шаг1.Выбираемпроизвольнуювершинуv}₁^{иполагаемчастичныйэйлеровциклC∗=}

^{v1^{}.ВграфеGбудемдвигатьсяотнекоторойвершинычастичногоциклаипомечать}

пройденныеребра.Помеченноеребробудемвключатьвэйлеровцикл.Полагаемi=1.

Шаг2.Двигаемсяотвершиныv_iпонепомеченнымребрамипомечаемихдотехпор,поканевернемсявv_i.ПустьприэтомпостроенциклC.

^{ЦиклCвключаемвC∗так,чтовначалеидутребраC∗довершиныv}_i^{,затемребрацикла}

_{CизатемоставшиесяребраC}^∗_.

Есливсеребраисходногографапомечены,тоэйлеровциклпостроен.Еслиестьнепоме-ченныеребра,тосуществуетвершинаv_j∈C^∗,котораяявляетсяконцомнепомеченногоребра.Пустьv_j–последняяизтакихвершин,входящаявC^∗.

Шаг3.УдаляемизграфаребрациклаC.Полагаемi=jипереходимкШагу2,т.е.строимновыйциклнанепомеченныхребрах,начинаясвершиныv_j.

Примеры.Дватреугольника,имеющиеобщуювершину.Двачетырехугольника,имею-щиеобщуюсторону,вершиныкоторойдополнительносоединеныцепью.