Графы. Теорема Эйлера
МИНИСТЕРСТВО ОБРАЗОВАНИЯ
РЕСПУБЛИКИ БЕЛАРУСЬ
|
Курсовая работа |
Студент _______________ А.О. Панов подпись, дата Руководитель подпись, дата
|
|
Витебск, 2013 |
СОДЕРЖАНИЕ
Введение
- Теоретическая часть
- Основные понятия теории графов
- Матричное представление графов
- Операции над графами
- Маршруты, цепи, циклы
- Расстояния в графах. Диаметр, радиус, центр графа
- Нагруженные графы. Определение кратчайших маршрутов
- Эйлеровы графы
- Теорема Эйлера
- Практическая часть
Заключение
Литература
ВВЕДЕНИЕ
Исторически сложилось так, что теория графов зародилась двести с лишним лет назад именно в ходе решения головоломок. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре общего внимания.
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.
В настоящее время эта теория находит многочисленное применение в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов, в программировании и теории игр, теории передачи сообщений. Теория графов теперь применяется и в таких областях, как экономика, психология и биология.
В этой работе мы подробнее рассмотрим эйлеровы графы, основные сведения и теоремы, связанные с этим понятием. А также задачи, которые решаются с помощью эйлеровых графов.
1. ТЕОРИЕТИЧЕСКАЯ ЧАСТЬ
1.1 Основные понятия теории графов
Граф G – пара (V,X), где V конечное непустое множество, содержащее p вершин, а множество Х содержит q неупорядоченных пар различных вершин из V.
Каждую пару X={u,v} вершин в Х называют ребром графа G и говорят, что Х соединяет u и v.Мы будем писать X=uv и говорить, что u и v – смежные вершины. Вершина u и ребро Х инцидентны, так же как v и Х. Если два различных ребра X и Y инцидентны одной и той же вершине, то они называются смежными. Граф с р вершинами и q ребрами называется (p;q)- графом. Граф (1,0)- называется тривиальным.
Если элементом множества V может быть пара одинаковых элементов u, то такой элемент множества V называется петлёй.
Типы графов:
- Мультиграф, в нём не допускаются петли, но пары вершин могут соединяться более чем одним ребром, эти рёбра называются кратными (рис.1).
- Псевдограф, в нём допускаются петли и кратные рёбра (рис.2).
Рис.1
- Ориентированный граф, или орграф, состоит из конечного непустого множества V вершин и заданного набора Х упорядоченных пар различных вершин. Элементы из Х называются ориентированными рёбрами, или дугами. Нет петель и кратных дуг (рис. 3).
- Направленный граф – это орграф, не имеющий симметричных пар ориентированных рёбер (рис.4).
- Помеченные графы (или перенумерованные), если его вершины отличаются одна от другой какими-либо пометками. В качестве пометок обычно используются буквы или целые числа.
Степенью вершины vi в графе G называется число рёбер, инцидентных vi ,обозначается di. Для орграфа вводятся понятия степени входа и выхода. Степенью выхода вершины v называется количество рёбер, для которых v является начальной вершиной, обозначается outdeg(v). Степенью входа вершины v называется количество рёбер , для которых v является конечной вершиной, обозначается indeg(v). Если indeg(v)=0, то вершина v называется источником. Если outdeg(v)=0, то вершина v называется стоком.
1.2 Матричное представление графов
Пусть G –помеченный граф порядка n, VG={1, 2, ... , n}. Определим бинарную n×n-матрицу A=A(G), положив
A(G) называется матрицей смежности графа G. Это симметричная матрица с нулями на диагонали. Число единиц в строке равно степени соответствующей вершины.
Очевидно, что соответствие G→A(G) определяет биекцию множества помеченных графов порядка n на множество бинарных симметричных n×n-матриц с нулевой диагональю.
Аналогично определяются матрицы смежности A мульти- и псевдографов: ik равно числу ребер, соединяющих вершины i и k (при этом петля означает два ребра).
Также определяется матрица смежности A(G) ориентированного графа.
Очевидно, что если A(G)– матрица смежности орграфа G порядка n, то
т.е. число единиц в i-й строке матрицы A(G) равно полустепени исхода i-й вершины, а число единиц в k-м столбце равно полустепени захода k-й вершины.
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одинаковыми перестановками строк и столбцов.
Теорема верна также для мультиграфов, псевдографов и орграфов.
Пусть G –(n, m)-граф, VG={1, 2, ... , n} EG={e1, e2,... , em}. Определим бинарную n×m-матрицу I=I(G) условиями
Матрица I называется матрицей инцидентности графа G. В каждом ее столбце ровно две единицы, равных столбцов нет. Как и выше, соответствие G→I(G) является биекцией множества помеченных (n, m)-графов с занумерованными ребрами на множество n×m-матриц, удовлетворяющих описанным условиям.
Матрица инцидентности I для орграфа:
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга произвольными перестановками строк и столбцов.
Теорема верна также для мульти графов, псевдо графов и орграфов.
Свойства матриц смежности и инцидентности:
1) Сумма элементов матрицы A(G), где G=(V, E)– мульти граф, V={v1, v2, ..., vn}, по i-йстроке (или по i-му столбцу) равна δ(vi). 2) Сумма элементов матрицы A(G), где G=(V, E)– ориентированный псевдо граф,
V={v1, v2, ... , vn}, по i-й строке и по i-му столбцу соответственно равны δ(vi), δ(vi).
3) Пусть G– ориентированный мульти граф с непустым множеством дуг. Тогда: а) сумма строк матрицы I(G) является нулевой строкой; б) любая строка матрицы I(G) является линейной комбинацией остальных строк; в) ранг матрицы I(G) не превосходит n–1; г) для любого контура матрицы G сумма столбцов матрицы I(G), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.
4) Пусть G– мульти граф с непустым множеством ребер. Тогда при покоординатном сложении по модулю 2: а) сумма строк матрицы I(G) является нулевой строкой; б) любая строка матрицы I(G) является суммой остальных строк; в) для любого цикла в G сумма столбцов матрицы I(G), соответствующих реб-рам, входящим в этот цикл, равна нулевому столбцу.
1.3 Операции над графами
Граф H называется подграфом графа G, если VH VG, EH EG. Если H – под-граф графа G, то говорят, что H содержится в G. Подграф называется собственным, если он отличен от самого графа.
Подграф H называется остовным подграфом графа G, если VH =VG.
Если множество вершин подграфа H есть U, а множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат U, то H называется подграфом, порожденным множеством вершин U, и обозначается G(U).
Если множество ребер подграфа H есть E' EG, а множество его вершин совпадает с множеством всех концов ребер из E' вершин графа G, то подграф H называется подграфом, порожденным множеством ребер E' и обозначается G(E').
Пусть v – вершина графа G. Тогда операцию построения графа H=G–v называют удалением вершины v. Построенный в результате этой операции граф H содержит все ребра множества ЕG кроме инцидентных вершине v, а VH =VG\{v}.
Пусть e – ребро графа G. Тогда операцию построения графа H=G–e называют удалением ребра e. Построенный в результате этой операции граф H содержит все вершины графа G, а EH =EG\{e}.
Удаление вершины или ребра, а также переход к подграфу – это операции, с помощью которых можно из имеющегося графа получать другие графы с мень-шим числом элементов.
Рассмотрим теперь операции, позволяющие получать из имеющихся графов графы с большим числом элементов.
Если вершины u и v графа G=(VG, EG) не смежны, то говорят, что граф H=(VH, EH) получен из графа G добавлением ребра e={u, v}, если VH =VG и EH = EG{e}, то пишут H=G+e.
Граф H называется объединением (или наложением) графов F и G, если H =VF∩VG и EH =EF∩EG. В этой ситуации пишут H=F∩G. Объединение F∩G называется дизъюнктивным, если VF ∩ VG =∅. Аналогично определяются объединение и дизъюнктивное объединение любого множества графов, причем в последнем случае никакие два из объединяемых графов не должны иметь общих вершин.
Пусть G1=(V1, E1) и G2=(V2, E2). Тогда произведением графов (обозначается G1×G2) называется такой граф G, для которого VG =V1×V2– декартово произведе-ние множеств вершин исходных графов, а EG определяется следующим образом: вершины (u1, u2) и (v1, v2) смежны в графе G тогда и только тогда, когда u1=v1, а u2 и v2 смежны в G2, или u2=v2, а u1 и v1 смежны в G1
1.4 Маршруты, цепи, циклы
Чередующаяся последовательность v1, e1, v2, e2, ... , en, vn+1 вершин и ребер графа такая, что ei =vivi+1 (i=1, n ), называется маршрутом, соединяющим вершины 1 и vn+1 (или (v1vn+1)-маршрутом). Очевидно, что для задания маршрута в графе достаточно задать последовательность v1, v2, ..., vn+1. его вершин, либо последовательность e1, e2,... , en его ребер.
Вершина v называется достижимой из вершины u, если существует (u, v)-маршрут. Любая вершина считается достижимой из себя самой.
Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Маршрут (1) называется циклическим, если v1=vn+1. Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом. Число ребер в маршруте называется его длиной. Цикл длины 3 часто называют треугольником. Длина всякого цикла не менее трех, если речь идет о простом графе, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом.
Свойства маршрутов, цепей и циклов:
1) Всякий незамкнутый (u, v)-маршрут, содержит в себе простую (u, v)-цепь. В частности, любая (u, v)-цепь, содержит в себе простую (u, v)-цепь. Причем, если (u, v)-маршрут содержит в себе вершину w (w≠u и w≠v), то в общем случае, простая (u, v)-цепь может не содержать в себе вершину w.
2) Всякий непростой цикл можно разбить на два или более простых. Причем для замкнутого маршрута такое утверждение не верно.
3) Всякая непростая (u, v)-цепь, может быть разбита на простую (u, v)-цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.
4) Для любых трех вершин u, w, v из существования (u, w)-цепи их и (w, v)-цепи, следует существование (u, v)-цепи. Причем может не существовать (u, v)-цепи, содержащей вершину w.
5) Объединение двух
Если два графа изоморфны:
1) то они одного порядка;
2) у них одинаковое количество ребер;
3) для произвольного i,0≤i≤n–1, (n – порядок графов) количество вершин степени i, у обоих графов одинаковое;
4) у них совпадают обхваты;
5) у них одинаковое
количество простых циклов
Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)-маршрут.
Теорема. Граф G=(V,E) связен тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы обе граничные точки каждого ребра находились в одном и том же множестве.
Всякий максимальный связный подграф графа G называется связной компонентой (или компонентой) графа G. Слово "максимальный" означает максимальный относительно включения, т.е. не содержащийся в связном подграфе с большим числом элементов. Множество вершин связной компоненты называется областью связности.
Для ориентированного графа вводится понятие ориентированного маршр-та – это последовательность вида (1), в которой ei=(vi,vi+1). Аналогом цепи в этой ситуации служить путь (ориентированная цепь). Аналогом цикла служит контур (ориентированный цикл).
Орграф называется сильносвязным, если любые две его вершины достижимы друг из друга. Орграф называется одностороннесвязным, если для любой пары его вершин по меньшей мере одна достижима из другой. Орграф называется сла-босвязным, если любые две вершины его основания соединены маршрутом. Орг-раф называется несвязным, если его основание несвязный псевдограф.
Теорема. Орграф является сильносвязным тогда и только тогда, когда в нем есть остовной циклический маршрут.
Необходимость. Пусть G – сильносвязный орграф и T=(v0, x1, v1,..., xn, v0) – его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G – сильносвязный орграф, то существуют маршруты T1=(v0, y1, ..., v), T2=(v, z1, ..., v0). Но тогда циклический маршрут T’=(v0, x1, v1, ..., xn, v0, y1, ..., v, z1, ..., v0) содержит большее число вершин, чем T, что противоречит выбору маршру-та T. Следовательно, T – остовной маршрут.
Достаточность. Пусть u и v – две произвольные вершины орграфа G, а T=(v0, x, ..., v, y, ..., u, z, ..., v0) – циклический маршрут. Тогда u достижима из v спомо-щью маршрута (v, y, ..., u)– части маршрута T,– а v из u – с помощью маршрута (u, z,..., v0, x, ..., v).3
Теорема. Орграф является одностороннесвязным тогда и только тогда, когда в нем есть остовной маршрут.
Теорема. Орграф является слабосвязным тогда и только тогда, когда в его основание есть связный псевдограф.
Сильносвязной компонентой орграфа называется его максимальный относительно включения сильносвязный подграф.
1.5 Расстояния в графах. Диаметр, радиус, центр графа
Пусть G = <V, U> - связный неорграф, Vi, Vj – две его несовпадающие вершины.
Длина кратчайшего (Vi, Vj)-маршрута называется расстоянием между вершинами Vi и Vj и обозначается через ρ (Vi, Vj).
Положим ρ (Vi, Vj) = 0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:
1) ρ (Vi, Vj) ≥ 0;
2) ρ (Vi, Vj) = 0 ↔ Vi = Vj
3) ρ (Vi, Vj) = ρ (Vi, Vj) – симметричность
4) ρ (Vi, Vj) ≤ ρ (Vi, Vj) + ρ (Vj, Vк) – неравенство треугольника.
Если V = {V1, V2,…, Vn}, то матрица Р = (рi,j) = ρ (Vi, Vj), называется матрицей расстояний (где матрица Р симметрична).
Для фиксированной вершины V величина Е (v) = мах { ρ (Vi, Vj) | Vj є V} называется эксцентриситетом вершины V. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее.
Если Р-матрица расстояний, то эксцентриситет Е (Vi) равен наибольшему из числе, стоящих в i-й строке.
Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d (G) : d (G) = vf[ {E(v) | v є V}. Вершина V называется периферийной, если Е (v) = d (G).
Минимальный из эксцентриситетов графа G называется его радиусом и обозначается через r (G) : r (G) = min {E (vi) | vi є V}.
Вершина V называется центральной, если Е (v) = r (G).
Множество всех центральных вершин графа называется его центром.
Задача нахождения центральных вершин возникает в практической деятельности людей. Пусть, например, граф представляет собой сеть дорог, т.е. вершины соответствуют населенным пунктам, а ребра – дорогам между ними. Требуется оптимально разместить больницы, пункты обслуживания и т.п. В подобных ситуациях оптимизация заключается в минимизации расстояния от места обслуживания до наиболее удаленного населенного пункта. Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи отличаются от этой идеальной темы, что приходится учитывать и другие обстоятельства – расстояния между населенными пунктами, стоимость, время проезда и т.д.
Расстоянием d (Vi, Vj) между вершинами Vi и Vj графа G называют длину кратчайшего пути, их соединяющего. (Если граф G-дерево, то путь соединяющий вершины Vi и Vj, единственный).
Наибольшее из таких чисел называют диаметром графа, наименьшее – радиусом графа.
По тем или иным причинам почти все работы по теории графов таят в себе семена возможных практических применений или по крайней мере потенциально полезны.
Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, экономике, биологии, медицине, в областях прикладной математики.
1.6 Нагруженные графы. Определение кратчайших маршрутов
Пусть G = <V,U>- взвешенный граф, имеющий n вершин и матрицу весов W = (wij), wij € R, где вес каждой дуги (Vi, Vj) есть некоторое вещественное число μ(Vi, Vj).
Весом маршрута V1, V2, Vn, Vn+1 называется число μ.
Взвешенным расстоянием (w-расстоянием) ρω(Vi,Vj) между вершинами Vi и Vj называется минимальный из весов Vi,Vj маршрутов.
(Vi,Vj) – маршрут, вес которого равен расстоянию ρω(Vi,Vj) , называется кратчайшим (Vi,Vj) – маршрутом во взвешенном графе G.
Взвешенным эксцентриситетом Eω(Vi) вершины Vi называется число max{ ρω(Vi,Vj)│Vj €V}
Взвешенной центральной вершиной графа G, называется вершина Vj , для которой Eω(Vi)=min{ Eω(Vi)│Vj €V}
Взвешенным эксцентриситет центральной вершины называется радиусом графа G и обозначается через rw(G).
Эйлеровы графы
Исторически топология и теория графов зародились при решении Эйлером задачи о Кенигсбергских мостах. Ее решение мы рассмотрим ниже. В результате решения этой задачи появился еще один вид графов - эйлеровы графы. Эйлеровым путем в графе называется путь, содержащий все ребра графа (т.е. проходящий по каждому ребру ровно по одному разу, но не обязательно замкнутый). Эйлеровым циклом в графе называется цикл, содержащий все ребра графа (т.е. это замкнутый эйлеров путь). Граф, обладающий эйлеровым циклом, называется эйлеровым графом. Интересные факты: В связном графе G существует эйлеров путь тогда и только тогда, когда не более двух его вершин имеют нечетную степень. Граф G является эйлеровым тогда и только тогда, когда он связен и степени всех его вершин четны. Таким образом, замкнутую фигуру, в которой все вершины четные, можно начертить одним росчерком без повторений, начиная обводить ее с любой точки.
Рассмотрим теперь знаменитую задачу о Кенигсбергских мостах. Задача формулируется следующим образом. Мосты через реку Прегель расположены как на рисунке.
- Теорема Эйлера.
Если многоугольник разбит на конечное число многоугольников так, что любые два многоугольника разбиения или не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство
В - Р + Г = 1, (*)
где В - общее число вершин, Р - общее число ребер, Г - число многоугольников (граней).
Доказательство. Докажем, что равенство (*) не изменится, если в каком-нибудь многоугольнике данного разбиения провести диагональ (рис. 2, а).
Действительно, после проведения такой диагонали в новом разбиении будет В вершин, Р+1 ребер и количество многоугольников увеличится на единицу. Следовательно, имеем
В - (Р + 1) + (Г+1) = В – Р + Г.
Пользуясь этим свойством, проведем диагонали, разбивающие входящие многоугольники на треугольники, и для полученного разбиения покажем выполнимость соотношения (*) (рис. 2, б). Для этого будем последовательно убирать внешние ребра, уменьшая количество треугольников. При этом возможны два случая:
а) для удаления треугольника ABC требуется снять два ребра, в нашем случае AB и BC;
б) для удаления треугольника MKN требуется снять одно ребро, в нашем случае MN.
В обоих случаях равенство (*) не изменится. Например, в первом случае после удаления треугольника граф будет состоять из В-1 вершин, Р-2 ребер и Г-1 многоугольника:
(В - 1) - (Р + 2) + (Г -1) = В – Р + Г.
Таким образом, удаление одного треугольника не меняет равенства (*). Продолжая этот процесс удаления треугольников, в конце концов мы придем к разбиению, состоящему из одного треугольника. Для такого разбиения В = 3, Р = 3, Г = 1 и, следовательно, B - Р + Г= 1. Значит, равенство (*) имеет место и для исходного разбиения, откуда окончательно получаем, что для данного разбиения многоугольника справедливо соотношение (*).
Заметим, что соотношение Эйлера не зависит от формы многоугольников. Многоугольники можно деформировать, увеличивать, уменьшать или даже искривлять их стороны, лишь бы при этом не происходило разрывов сторон. Соотношение Эйлера при этом не изменится.
- Практическая часть
- Существует ли эйлеров цикл в графе G. Если существует, найдите его.[2]
Решение:
А) Так как каждая вершина
имеет чётную степень, то по
критерию в этом графе
Б) В этом графе также каждая вершина имеет чётную степень, значит, существует и эйлеров цикл: 1,2,3,4,5,3,1,4,5,2,1
В) Здесь каждая вершина имеет степень 5, то есть нечётную, следовательно, в этом графе (по критерию) нет эйлерова цикла.
- Где на выставке следовало бы сделать вход и выход (рис.8) , чтобы можно было провести экскурсию по всем залам, побывав в каждом из них в точности один раз?[2]
Решение:
В этом графе вершины А и В имеют степень 3, то есть нечётную, следовательно, в нём существует эйлеров путь с началом в одной из этих вершин и концом в другой. Значит, вход и выход следует установить в вершинах А и В.
3. Среди приведённых ниже графов найдите те, которые имеют эйлеров цикл.[1]
Решение:
а) Т.к. этот граф связный и каждая его вершина имеет чётную степень, то по критерию эйлерова графа, данный граф имеет эйлеров цикл:
a b e j i f c b d h j g f a c d e h g i a
б) Этот граф связный, но т.к. все его вершины имеют нечётную степень, то он не имеет эйлерова цикла.
в) Этот граф связный, но т.к. все его вершины имеют степень 3, то есть нечётную, то он не имеет эйлерова цикла.
г) Данный граф связный, степени вершин а и с имеют нечётную степень, значит, этот граф не имеет эйлерова цикла.
4. Среди приведённых ниже графов найдите те, которые имеют эйлеров цикл.[1]
Решение:
а) Граф не является связным, то есть не выполняется первое условие критерия, значит, он не имеет эйлерова цикла.
б) Этот граф является связным и все его вершины имеют чётную степень, значит, по критерию эйлерова графа, он имеет эйлеров цикл:
a c f h I j k g d c b f I l j g e d a
в) Данный граф связный, но степени вершин а и е нечётные, следовательно по критерию, этот граф не имеет эйлерова цикла.
г) Граф является связным, но так как все его вершины имеют нечётную степень, то граф не имеет эйлерова цикла.
5. Среди приведённых ниже графов найдите те, которые имеют собственный эйлеров путь.[1]
Решение:
а) Граф связный, и только две его вершины (a и f) имеют нечётную степень, следовательно, то по теореме 3, граф имеет собственный эйлеров путь.
б) Граф связный; deg(a)=3, deg(b)=3, deg(c)=3, то есть более двух вершин имеют нечётную степень, значит, не имеет эйлерова пути.
в) Этот граф связный и только две вершины (с и j) имеют нечётную степень, значит, граф имеет собственный эйлеров путь.
г) Граф связный; deg(a)=3, deg(b)=4, deg(c)=1, deg(d)=3, то есть более двух вершин имеют нечётную степень, следовательно, в этом графе нет эйлерова пути.
6. Среди приведённых ниже графов найдите те, которые имеют собственный эйлеров цикл.[1]
Решение:
а) Данный граф связный; deg(a)=3, deg(b)=2, deg(c)=3, deg(d)=2, deg(e)=2. Ровно две вершины имеют нечётную степень, значит, по теореме 3, граф имеет собственный эйлеров путь.
б) Граф является связным и ровно две его вершины (е и f) имеют нечётную степень, значит, данный граф имеет собственный эйлеров путь.
в) Граф связный, найдём степени вершин: deg(d)=5, deg(b)=5, deg(e)=5, нашлись три вершины, степень которых нечётная, значит, граф не имеет эйлерова пути.
г) Данный граф связный и только две его вершины (а и b) имеют нечётную степень, значит, этот граф имеет собственный эйлеров путь.
7. Какие из следующих
Решение:
а) Граф связный, найдём степени входа и выхода вершин (по теореме 5 степени входа и выхода каждой вершины должны совпадать):
indeg(a)=2, outdeg(a)=1, то есть нашлась вершина, у которой не совпадают степени входа и выхода, значит, граф не имеет эйлерова цикла.
б) Граф связный, найдём степени вершин:
indeg(a)=2 outdeg(a)=2
indeg(b)=2 outdeg(b)=2
- Гра як засіб підвищення мовленнєвої активності першокласників
- Гра, як засіб соціалізації дітей молодшого шкільного віку
- Гра як метод навчання. Її пізнавальне та виховне значення
- Гра як психологічний розвиток молодших школярів
- Гребная электрическая установка пассажирского теплохода
- Гребные электрические установка (ГЭК)
- Грегор Мендель
- Графо - моторные нарушения у первоклассников с ОНР
- Граффити, как вид искусства
- Граффити как средство языковой коммуникации молодежных сообществ
- Графы-деревья
- Графы и их применение
- Графы и их применение в решении задач
- Графы. Поиск оптимального маршрута по городам Беларуси
