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

Каждая из этих-сумм, очевидно, 1авна числу дуг орграфа 1Г|-. Сумма отап0Н0й всех вержп oprpaiTja G равна удвоенному числу д у г : . . ( 2 . 3 ) -1Р&М ' Например, ;,та орграфа, язображанного на рис.2.5, имеем tflV,). =3; =2; =5; =2» С^Ыг.у =5; ^ dLiTi) §2.6. Отношения ti гтайы. Отобтаясания. индуттоур.ше ГБЙ Д НМВ Быявям таонуЕ онязь понятий графа, отношения и стобрадсения. Пуоть 6 - ( V j Г ) _ орграф. Очевидно, Г С. и,, следова­ тельно, является бинарным ОТНОШС.:ИР "! на V . Если R V'^ .где V - конечное непустое множество, то пара являетоя оргра­ фом. Таким образом, теорию графов можно считать частным случаем теории отношений. Отображеше r . ' V j ^ V , индуцируемое орграфом оп­ ределяется так: ' i v & V Г(1г) = : СЩт/г) е г } , Возможно обратное поотроение. Если^:'^/-''У - отсбражение, то графем этого отображения называетоя орграф - ( V ,Г ) , где i - : vbV Как видпм, граф может быть задан заданием некоторого отображения на конечном множестве. В дальнейшем будем употреблять тарлины "образ" и "прообраз" вершины графа, имея в виду отображение Г , индуцируемое ооот- ветствя^ицим графом. ГЛАВА 3 . М^1РШЕУТЫ. СВЯЗНОСТЬ. ДОСТЙШОСТЬ , Структурную характеристику г рфов дают понятия достияимоо- т:- и связности. Приведем некоторые основные результаты, связан­ ные о этиьга понятиями.. ^3.1. и а ш т т в гтаФах Маршрутом в rpa^ie J называется такая чередующаяся' последовательность вершин и ребер,' натанавдаяся и оканчшаицая- Ья вершнами, что;каадса ребро в ней инцидентно предадущей и по- оледущей вершинам. Пример запяои маршрута; • Этот маршрут соединяет вершинн "Щ к iK, , которые называются кон­ цами мардрут а . Такой маршрут называют также СЩ - ' Л ) - маршру­ том. Если это не может приверти к нвдорвзумедиям,,...п^ ;• -''Г •" 'ч ' • I ' ^ ; • : " V