Начертите полный граф который имеет 7 вершин
Перейти к содержимому

Начертите полный граф который имеет 7 вершин

  • автор:

Начертите полный граф который имеет 7 вершин

Под графом мы будем понимать множество точек ( вершин ), некоторые из которых соединены отрезками ( ребрами ).
Степень вершины графа — это количество выходящих из нее (или, что то же самое, входящих в нее) ребер (еще говорят: количество ребер, инцидентных данной вершине). Вершина графа называется четной , если ее степень четна, и нечетной в противном случае.
Некоторая часть вершин данного графа называется компонентой связности , если из любой ее вершины можно «дойти» до любой другой, двигаясь по ребрам.

В некоторых случаях на ребрах графа выбирается «направление движения» (например, когда на автомобильной дороге вводится одностороннее движение). При этом получается ориентированный граф . (Если направление движения по ребрам не определено, то граф называется неориентированным ). В ориентированном графе различают положительную и отрицательную степень каждой вершины (то есть количество ребер, соответственно, входящих и выходящих из нее). Две вершины могут быть соединены и несколькими ребрами, направления движения по которым противоположны («дорога с двусторонним движением»). Изменяется понятие компоненты связности: теперь каждый «маршрут» от одной вершины до другой должен учитывать направление движения по ребрам.

Задачи

1. Между девятью планетами Cолнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон — Меркурий, Меркурий — Венера, Уран — Нептун, Нептун — Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. По каждому маршруту ракеты летают в обе стороны. Можно ли долететь на рейсовых ракетах от Земли до Марса?

Решение.
Построим граф, вершинами которого являются планеты Солнечной системы, а ребрами — существующие маршруты рейсовых ракет. Изобразив такой граф на рисунке, нетрудно заметить, что он состоит из двух компонент связности (на нашем рисунке они выделены разными цветами). Земля и Марс оказываются в разных компонентах связности, поэтому долететь от Земли до Марса на рейсоых ракетах нельзя.

2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу?

Ответ. На рисунке указано одно из возможных решений (клетки пронумерованы в том порядке, в котором их обходит конь).

3. Можно ли, сделав несколько ходов конями из исходного положения (верхний рисунок), расположить их так, как показано на нижнем рисунке? (Выходить за пределы поля 3×3 не разрешается.)

Решение. Пронумеруем клетки поля 3×3, как показано на рисунке слева. Построим граф, вершинами которого являются эти клетки. Две клетки соединим ребром графа, если из одной в другую можно попасть за один ход коня. Расположим вершины графа так, как показано на рисунке справа, и проведем все ребра. Отметим на этом рисунке начальное и конечное местоположение коней. Для того, чтобы осуществить требуемую перестановку коней, нужно по крайней мере, чтобы, например, один из черных коней «перепрыгнул» через одного из белых. Но кони ходят по очереди, и ни в какой момент времени на одной клетке не могут оказаться два коня сразу. Поэтому осуществить такое «перепрыгивание» невозможно. Стало быть, невозможно и переставить коней требуемым образом.

4. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9?

Построим граф, вершинами которого являются города, а ребрами — существующие авиалинии. Вспомним признак делимости на 3: натуральное число делится нацело на 3 тогда и только тогда, когда сумма его цифр делится на 3. Заметим, что если название города делится на 3, то он соединен авиалиниями только с городами, названия которых тоже делятся на 3. Наоборот, те города, названия которых не делятся на 3, не могут быть соединены авиалиниями с городами, названия которых делятся на 3. Поэтому города 3, 6 и 9 образуют одну компненту связности графа, в которую никакие другие города не входят. Это означает, что из города 1 в город 9 добраться по воздуху нельзя.

Упражнение: А какие еще компоненты связности есть в этом графе?

5. В государстве 100 городов. Из каждого города выходит 4 дороги. Сколько всего дорог в государстве?

Решение. Обойдем по очереди все города, считая дороги, входящие из них. Всего таким способом мы насчитаем 400 дорог. Но каждая дорога выходит из двух городов, значит, каждую дорогу мы посчитали два раза. Поэтому на самом деле дорог в государстве в два раза меньше, чем мы насчитали, то есть 200.

Теорема 1. Количество ребер в любом графе равно половине суммы степеней его вершин.
Докажите эту теорему самостоятельно по аналогии с задачей 5.

6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Подсказка: попытайтесь посчитать количество телефонных проводов.

Решение. В качестве вершин графа возьмем телефоны, а в качестве ребер — телефонные провода. Применим к этому графу теорему 1. Степень каждой вершины графа равна 5, значит, сумма степеней всех вершин равна 5·15=75. Это нечетное число, поэтому его половина — число нецелое. То есть в нашем графе нецелое число ребер, и в городе нецелое число проводов, чего быть не может.

Следующую задачу в силу ее важности сформулируем в виде теоремы. 7. Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин.

Доказательство. По теореме 1 количество ребер графа равно половине суммы степеней всех вершин графа. Все вершины графа делятся на четные и нечетные. Сумма степеней четных вершин графа всегда четна. А вот сумма нечетного количества нечетных чисел нечетна, поэтому если нечетных вершин нечетное количество, то сумма их степеней будет нечетна. Тогда сумма степеней всех вершин графа будет нечетна. Половина этой суммы будет нецелым числом, то есть в графе нецелое число ребер, а такого быть не может. Полученное противоречие доказывает, что количество нечетных вершин графа не может быть нечетным.

При решении всех последующих задач мы будем пользоваться этой теоремой. Любое решение следует начинать с выбора вершин и ребер графа. Попробуйте решить эти задачи самостоятельно, не ссылаясь на теорему, а заново проводя ее доказательство в каждом конкретном случае.

8. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 — по 4 друга, а 10 — по 5 друзей?

Решение. Сделаем учеников вершинами графа, а ребрами будем соединять тех из них, которые дружат между собой. По условию в таком графе четных вершин будет 11, а нечетных 9+10=19, то есть нечетное число, что противоречит теореме 2.

9. Школьник Вася Пупкин сказал своему приятелю Вите Иванову:
— У нас в классе тридцать пять человек. И представь, каждый из них дружит ровно с одиннадцатью одноклассниками.
— Не может этого быть, — сразу же ответил Витя Иванов, победитель математической олимпиады.
Почему он так решил?

Решение. Решение этой задачи полностью аналогично решению задачи 6.
10. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Решение. Сделаем вассалов вершинами графа; ребрами соединим тех из них, которые являются соседями. По условию все вершины этого графа нечетны, а всего их 19, то есть тоже нечетное число. Но по теореме 2 такого быть не может.

11. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение. Сделаем города вершинами графа, а дороги — его ребрами. По условию в этом графе 100 ребер, а по теореме 1 число ребер равно половине суммы степеней всех вершин. Значит, сумма степеней всех вершин равна 200. Но степень каждой вершины по условию равна 3, а 200 не делится на 3. Полученное противоречие доказывает, что такого быть не может.

12. В школе 953 ученика. Одни из них знакомы, другие не знакомы друг с другом. Доказать, что хотя бы у одного из них число знакомых среди учеников этой школы чётно.

Решение. Сделаем учеников вершинами графа и будем соединять ребрами тех из них, которые знакомы друг с другом. Если бы у всех школьников число знакомых среди учеников этой же школы число знакомых было нечетно, то все 953 вершины нашего графа были бы нечетными, что противоречит теореме 2. Значит, есть по крайней мере один школьник, у которого число знакомых среди учеников этой же школы четно. Более того, можно сказать, что таких школьников обязательно должно быть нечетное число (подумайте почему).

13. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

Решение. Сделаем всех людей, когда-либо живших на Земле, вершинами графа, а рукопожатия — его ребрами. (При этом две вершины могут соединяться и несколькими ребрами; такие ребра называют кратными .) Люди, сделавшие нечетное число рукопожатий, — нечетные вершины такого графа, поэтому по теореме 2 их количество четно.

14*. Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4 и 2 соответственно.

Решение. У каждой из первых четырех вершин степень 4, то есть каждая из этих вершин соединена ребрами со всеми остальными (поскольку всего вершин 5). В частности, каждая из этих четырех вершин соединена и с пятой вершиной. Поэтому если в графе с пятью вершинами четыре вершины имеют степень 4, то и оставшаяся вершина должна иметь степень 4.

15*. Можно ли расположить в пространстве 9 шаров так, чтобы каждый из них касался ровно пяти других?

Решение. Сделаем вершинами графа шары и соединим ребрами те из них, которые касаются друг друга. По условию в таком графе будет нечетное число нечетных вершин, что противоречит теореме 2.

16*. а) Можно ли нарисовать на плоскости 8 отрезков так, чтобы каждый пересекался ровно с тремя другими? б) Тот же вопрос для 9 отрезков.

Ответ. а) Да, см. рисунок; б) нет.

Решение. Сделаем отрезки вершинами графа и соединим ребрами те из них, которые пересекаются между собой. По условию п. б) в таком графе нечетное число нечетных вершин, что противоречит теореме 2. Для пункта а) это рассуждение не годится, однако это еще не означает, что сделать такой рисунок возможно. Чтобы это доказать, надо его нарисовать. Для этого достаточно придумать рисунок с 4 отрезками, каждый из которых пересекается ровно с тремя другими, а потом изобразить два таких рисунка рядом. (Здесь важно, что в условии фигурируют именно отрезки, а не прямые.)

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!


полный граф — Дискретная математика — Ответ 5363131

Author24 — интернет-сервис помощи студентам

Существует ли полный граф с данным количеством рёбер?
Существует ли ПОЛНЫЙ граф у которого кол-во ребер равно: a)15 b)18 c)8k^2+2k, k Є N. Объясните.

Сколько графов-циклов содержит полный граф с n вершинами?
Сколько графов-циклов содержит полный граф с n вершинами? Каким-то магическим способом я дошёл к.

Как преобразовать неориентированный граф в ориентированный граф из матричной записи
Есть ли какой нибудь алгоритм преобразования Неориентированный графа в ориентированный граф из.

Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством пересечений
Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством.

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Полный граф
Задание Напишите программу,которая с помощью данной нам матрицы, представленного в виде двумерного.

Полный граф
Для заданного списком рёбер графа проверить, является ли он полным. Входные данные Первая.

Полный граф по матрице инциденции
Граф задан матрицей инциденции. Определить является ли он полным. Достроить до полного графа если.

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

Тест «Графы»
тест по теме

1.2. Полный граф имеет 7 вершин, то количество ребер будет равно:

а) 14; б) 21; в) 7; г) 42.

1.3. Какие из указанных в графе на рисунке маршрутов являются путем?

а) АВГВД б) АВГ в) АВДАБ г) АБВАД

1.4. Какие из указанных циклов являются простыми ?

а) АВГА б) АБВГБА; в) ВБАГВ; г) ДВАГВД

1.5. Хроматическое число графа на рисунке равно:

а) 3; б) 6; в) 4; г) 2.

2.1. Сколько ребер нужно провести чтобы достроить граф, изображенный на рисунке до полного?

2.2. Назвать наибольшее число висячих вершин, дерева с 10-ю вершинами .

2.3. Укажите критерий эйлеровости графа.

3. 1 . Изобразите с помощью графа договорные отношения между предприятиями А, Б, В, Г, Д, Е, если к рассматриваемому моменту:
предприятие А установило договорные отношения со всеми другими предприятиями;
Б установило с Г и Д;
В установило со всеми предприятиями, кроме предприятия Е.
Сколько вершин и сколько ребер имеет полученный граф?

3.2. Представьте выражение 14+с*а помощью ориентированного упорядоченного дерева.

Тема: Теория графов

1.1. На рисунке изображен :

а ) Полный граф; б) неполный граф; в) граф типа «дерево» г) нулевой;

1.2. Полный граф имеет 9 вершин, то количество ребер будет равно:

а) 18; б) 72; в) 9; г) 36.

1.3. Какие из указанных в графе на рисунке маршрутов являются путем?

а) АВГВБ б) АВГВ в) АВДАГ г) АБВ

1.4. Какие из указанных циклов являются простыми ?

а) АВГДВА б) АБВГВА; в) ВБАГВ; г) ДВАГВД

1.5. Хроматическое число графа на рисунке равно:

а) 3; б) 6; в) 4; г) 2.

2.1. Сколько ребер нужно провести, чтобы достроить граф, изображенный на рисунке, до полного?

2.2. Назвать наименьшее число висячих вершин, дерева с 15-ю вершинами

2.3. Сформулируйте достаточные условия гамильтоновости графа.

3.1. Среди семи стран установлены экономические отношения, причем каждая страна имеет экономические договоры с каждой другой страной. Изобразите в виде графа результат установленных экономических отношений. Сколько вершин и ребер имеет полученный граф?

3.2. Представьте выражение 25: (а-в) с помощью ориентированного упорядоченного дерева.

Начертите полный граф который имеет 7 вершин

  • Исследовательские работы
  • Методические материалы
  • Игры, тренажеры, тесты
    • Игры и тесты по окружающему миру
    • Игры и тренажеры по математике

    Обучающие программы и исследовательские работы учащихся

    Помогаем учителям и учащимся в обучении, создании и грамотном оформлении исследовательской работы и проекта.

    Темы исследований

    Оформление работы

    • Виды исследовательских работ
    • Организация и проведение работы
    • Этапы исследовательской работы
    • Оформление исследовательской работы
    • Структура исследовательской работы
    • План исследовательской работы
    • Титульный лист исследовательской работы
    • Содержание исследовательской работы
    • Введение исследовательской работы
      • Обоснование актуальности исследования
      • Проблема исследовательской работы
      • Цель исследовательской работы
      • Объект и предмет исследования
      • Задачи исследовательской работы
      • Гипотеза исследовательской работы
      • Методы исследования
      • Теоретическая значимость работы
      • Практическая значимость работы

      Объявление

      Наш баннер

      Сайт Обучонок содержит исследовательские работы и проекты учащихся, темы творческих проектов по предметам и правила их оформления, обучающие программы для детей.

      Будем благодарны, если установите наш баннер!

      Баннер сайта Обучонок

      Код баннера:

      Исследовательские работы и проекты

      Виды графов

      Пт, 27/01/2017 — 12:32 | nikolay
      Исследовательская работа:

      1.2. Виды графов

      Виды и схемы графов

      Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)

      Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)

      Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)

      Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.

      Графы в строительстве

      Стрелка от одной работы к другой на графе, изображенном на рисунке, означает последовательность выполнения работ.

      Нельзя начинать монтаж стен, не закончив строить фундамент, чтобы приступить к отделке, нужно иметь на этажах воду и т. д.

      Степени вершин и подсчет числа ребер.

      Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

      Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

      Граф с пятью вершинами

      На рисунке 5 изображен граф с пятью вершинами.

      Степень вершины А обозначим Ст.А.

      На рисунке:
      Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

      Сформулируем некоторые закономерности, присущие определенным графам.

      Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

      Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

      Эта закономерность справедлива не только для полного, но и для любого графа.

      Число нечетных вершин любого графа четно.

      Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.

      Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

      Эйлеровы графы.

      Эйлеровые графы

      Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.6)

      Такими графы названы в честь учёного Леонарда Эйлера.

      Закономерность 3. (вытекает из рассмотренной нами теоремы).
      Невозможно начертить граф с нечетным числом нечетных вершин.

      Закономерность 4. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.

      Закономерность 5. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.

      Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».

      Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.

      Связные графы.

      Связные графы

      Граф называется связным, если любые две его вершины могут быть соединены путем, т. е. последовательностью ребер, каждое следующее из которых начинается в конце предыдущего.

      На рисунке 7, очевидно, изображен несвязный граф.

      Граф называется несвязным, если это условие не выполняется.

      Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным.(рис.8)

      Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.

      Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа. (рис.8)

      Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности.

      Граф является эйлеровым тогда и только тогда, когда он связен и имеет не более двух нечетных вершин.

      Деревья.

      Деревом называется любой связный граф, не имеющий циклов.

      Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

      Циклом называется путь, в котором совпадают начало с концом.

      Циклы Элементарный и Эйлеровая линия

      Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом.

      Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а).

      В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.

      Путем в графе от одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами.

      При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.

      Висячие вершины в графах

      Висячей вершиной называется вершина, из которой выходит ровно одно ребро (рис.10).
      (кружком обведены висячие вершины).

      Для каждой пары вершин дерева существует единственный путь, их соединяющий.

      Этим свойством пользуются при нахождении всех предков в генеалогическом дереве, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева, которое является «деревом» и в смысле теории графов.

      Всякое ребро в дереве является мостом.

      Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

      Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.

      (о висячей вершине). В каждом дереве есть висячая вершина.

      . В дереве число вершин на одну больше числа ребер.

      Изоморфизм. Плоские графы и теорема Эйлера.

      Два графа называются изоморфными, если у них поровну вершин, и вершины каждого графа можно занумеровать числами от 1 до n, так, чтобы вершины первого графа были соединены ребром тогда и только тогда, когда соединены ребром соответствующие вершины второго графа.

      Изоморфные графы

      Докажем, что графы изображенные на рисунке 11 изоморфны.

      Пронумеруем вершины первого и второго графов от 1 и до 4 (рис.12).

      В первом графе соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4; заметим, что во втором графе также соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4, следовательно, данные графы изоморфны.

      Для того, чтобы выяснить, изоморфны ли два графа, нужно убедиться в том, что у них:

      • одинаковое количество вершин
      • если вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены ребром.

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

      Эйлера. Для правильно нарисованного связного плоского графа имеет равенство: V-E+F=2, где V – число вершин, E — число рёбер, F – число кусков.(равенство V -E+F=2 обычно называют формулой Эйлера).

      Граф, каждая вершина которого соединена с ребром любой другой вершины, называется полным.

      Теорема Понтрягина – Куратовского

      Понтрягина – Куратовского. Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами.

      (В основном используется в старинных задач о домах и колодцах, суть которой сводится к выяснению вопроса — является ли рассматриваемый граф плоским или нет, рис.13)

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

      Существуют значительные классы практических задач, которые решить с помощью ранее рассмотренных типов графов невозможно.

      Так, например, схема дорог и площадей города изображается с помощью плоского графа. Но если нужно этой схемой воспользоваться с целью проезда по городу на автомашине, а движение на отдельных (или на всех) улицах одностороннее?

      Тогда могут помочь сориентироваться в этой ситуации стрелки, расположенные, например, прямо на ребрах — улицах рассматриваемой схемы (графа) города.

      Граф, на рёбрах которого расставлены стрелки, называется ориентированным.

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

      Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих» из вершины).

      Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих» в вершину).

      Так, на рисунке 15 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:
      Ст.вх.А=2, Ст.вых.А=1 Ст.вх.В=2, Ст.вых.В=0 Ст.вх.Д=1, Ст.вых.Д=3.

      Примеры путей в ориентированном графе

      Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер A1A2, A2A3, . Аn-1Аn, в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.

      На рисунке.15 показаны примеры путей в ориентированном графе. Причем, первые два пути простые — ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым ,т. к. через вершину Г путь «проходил» дважды.

      Ориентированным циклом называется замкнутый путь в ориентированном графе.

      На рисунке 15 приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.

      Кратчайшие пути между вершинами графа

      Так, на рисунке 16 пути от А к Д могут быть различны и иметь различную длину.
      Первый путь имеет длину 2, второй — 3,
      а третий — 4.

      Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними. Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2.

      Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным(обозначают значком бесконечности). Так, расстояние между вершинами Б и Д графа, представленного на рисунке 17 бесконечно: S(БД) = ∞

      Ориентированные графы в экономике активно используются в сетевом планировании, в математике — в теории игр, теории множеств; при решении многих задач, в частности, комбинаторных.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *