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

Задание 2

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

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

Единица в шестой строке на главной диагонали говорит о том, что шестая вершина имеет дугу-петлю. Вершины 4 и 6 имеют противоположно направленные дуги, т. к. соответствующие элементы матрицы, симметричные главной диагонали, заполнены. Число 2 в пересечении четвёртой строки и второго столбца означает, что от вершины 4 к вершине 2 направлена пара кратных дуг. Строки матрицы соответствуют выходным окрестностям вершин, а столбцы — входным окрестностям. Сумма элементов по строке равна полустепени исхода соответствующей вершины, а сумма элементов по столбцу — полустепени захода. Вершине-истоку 1 соответствует нулевой столбец 1 и ненулевая строка 1, а вершине-стоку 5 соответствует нулевая строка 5 и ненулевой столбец 5. Изолированной вершине 7 соответствует нулевая строка 7 и нулевой столбец 7.

Дуге-петле с номером 13 в матрице инцидентности соответствует единственная единица в 13 столбце, расположенная в строке вершины 6, которой она принадлежит. Столбцы 10 и 11 одинаковы, следовательно, соответствующие дуги являются кратными. Столбцы 14 и 9 станут одинаковыми, если в них поменять местами -1 и 1, следовательно, соответствующие им дуги противоположно направлены. Количество -1 в любой строке равно полустепени исхода соответствующей вершины, а количество 1 равно полустепени захода. Изолированной вершине 7 соответствует нулевая 7-ая строка. Вершине-истоку 1 соответствует 1 строка, в которой имеются -1 и нет 1. Вершине-стоку 5 соответствует 5 строка, в которой имеются 1 но нет -1.

Дуге-петле с номером 13 соответствует столбец матрицы списка дуг, в котором элементы равны между собой и равны номеру вершины, которой эта дуга принадлежит. Дуги 10 и 11 кратны, им соответствуют одинаковые столбцы в матрице. Противоположно направленным дугам 9 и 14 соответствуют столбцы матрицы, которые оказываются одинаковыми, если в одном из них переставить местами элементы. Полустепень исхода любой вершины — количество повторений ее номера в первой строке матрицы, а полустепень захода — количество повторений ее номера во второй строке матрицы. Изолированная вершина 7 имеет номер, который не встречается ни в первой, ни во второй строке. Вершина-исток 1 имеет номер, который встречается в первой и не встречается во второй строке, а вершина-сток 5 имеет номер, который встречается во второй и не встречается в первой строке.

Матрицы окрестностей вершин

В массивах FO(FI) хранятся номера вершин, являющихся выходами (входами) дуг. В массиве KAO хранятся номера элементов массива FO(FI), с которых начинается новая окрестность. Как видно из матриц, всего в графе 8 окрестностей по входящим и выходящим дугам.

На примере разберём составление матрицы окрестностей вершин по выходящим дугам. Окрестность первой вершины содержит 3 дуги. 3 вершина является концом первой дуги. 4 вершина является концом второй дуги . 2 вершина является концом третьей дуги. Окрестность второй вершины содержит 2 дуги. Далее матрица строится по этому принципу. Матрица окрестностей вершин по входящим дугам строится аналогично.

Построить связанный ориентированный граф, содержащий 5 сильных компонент связанности мощностью 4, 5, 6, 7, 1. Свернуть граф по найденным компонентам.

В отчете представить граф, раскрашенный по компонентам и граф-свертку.

Построить связанный ориентированный ациклический непоследовательный граф, состоящий из 5 порядковых уровней мощностью 3, 4, 2, 4, 3. Граф содержит 3 истоков и 3 стока. Свернуть граф по найденным уровням. В отчете представить граф, упорядоченный по уровням слева направо и граф-свертку.

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

Изменяя веса на дугах модифицировать граф так, чтобы кратчайшие пути по сумме весов и по количеству дуг между истоком и стоком не имели ни одной общей дуги (не совпадали). В отчете представить граф с выделенными путями, указать длину путей по весам и по количеству дуг. (1 картинка)

На этом же графе построить исходящее дерево кратчайших путей с корнем в истоке и заходящее дерево кратчайших путей с корнем в стоке.

Кратчайшие пути от вершины

Вершина-исток — 1, вершина сток — 25. Между истоком и стоком существует более пяти путей, длиной более пяти дуг.

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

Задание 6.1. Нарисуйте граф с семью вершинами и шестью ребрами, не имеющий ни одного цикла.
Задание 6.2. Нарисуйте связный граф с семью вершинами и шестью ребрами.
Задание 6.3. Нарисуйте граф с семью вершинами, в котором для любых двух вершин существует один и только один связывающий их путь.
Все предлагаемые решения выносим на доску, обсуждая каждый предложенный ребятами вариант.
Рассмотрим внимательно рисунки, которые строили при ре­шении этих заданий. Что характерно для всех построенных графов? Во-первых, они связные; во-вторых, они не содержат цик­лов. Такие графы выделяются в отдельный класс, представители которого именуются деревьями.

Рис 36
Деревом называется всякий связный граф, не имеющий циклов (рис. 36).
Будем считать, что граф, состоящий из одной изолирован­ной вершины, тоже является деревом.
Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке 36 висячие вершины выделенызакрашенными кружками).

Рис. 37
Лесом называется несвязный граф, представляющий объединение деревьев (рис. 37).
Задача 6.1.
В парке "Лотос" невозможно найти такой маршрут для прогулок по
его дорожкам, который начинается и оканчивается в одной и той же точке и каждую дорожку парка содержит не более раза. Докажите, что некоторые дорожки парка приводят в тупик.
Решение.
Построим граф G, в котором вершины соответствуют перекресткам и тупикам парка, а ребра — его дорожкам.
По условию задачи в графе Gнет циклов, и он является деревом. Существование тупиков в парке эквивалентно существованию висячих вершин в построенном дереве.
Предложение 2. В любом дереве есть висячая вершина. Предположим противное. Рассмотрим произвольную вершину v1 и перейдем из нее по любому ребру в вершину v2. Поскольку степень вершины v2не меньше двух, то из нее по новому ребру можно перейти в вершину v3 и так далее. Но число вершин в графе G конечно. Поэтому, в конце концов, мы приедем в одну из тех вершин, в которых были раньше (см. рис. 38).

Рис. 38
Это означает существование цикла в дереве G, что противоречит условию. Следовательно, в графе есть висячая вершина. Эта вершина будет соответствовать тупику в парке.
Задача 6.2.
Администрация парка "Лотос" (см. предыдущую задачу) решила про­
вести реконструкцию освещения парка. По новому проекту каждый
перекресток и тупик, должен будет освещаться четырьмя светильника­ми, а аллея, соединяющая два перекрестка или перекресток и тупик – шестью. Сколько светильников будет установлено, если в парке 18 перекрестков и тупиков.
Решение.
В предыдущей задаче мы установили, что граф G, описываю­щий перекрестки, тупики и аллеи парка "Лотос" является деревом. Най­дем соотношение между числом вершин и ребер любого дерева. Каждое дерево имеет висячую вершину (см. предыдущую задачу). Удалим вися­чую вершину v0 из дерева Gвместе с ребром, выходящим из этой вер­шины. Полученный граф G1 будет связным, и в нем будут отсутствовать циклы, т.е. граф G1 – также дерево. Из графа G1, найдя и затем удалив висячую вершину v1 вместе с выходящим из нее ребром, можно получить дерево G2 и так далее. Выполнив такие операции, мы получим последо­вательность деревьев, которая оканчивается деревом, состоящим из од­ной вершины и не имеющим ребер. Для этого дерена выполняется соот­ношение: m = n – 1, где n – число вершин графа, а m – число его ребер. Теперь будем добавлять в обратном порядке ранее удаленные вершины и ребра. При каждом возвращении добавляется одна вершина и одно ребро, и для каждого получающегося графа соотношение m = n – 1 будет выпол­няться. Следовательно, мы доказали теорему 9: в любом дереве число ребер на единицу меньше числа вершин.

Поскольку в парке 18 перекрестков и тупиков, то дерево Gбудет иметь 18 вершин и 17 ребер. В парке необходимо установить 18*4 + 17*6 = 174 светильника.

Начерти многоугольник имеющий 7 вершин Расскажи план выполнения работы

Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.

Определяющие черты новгородской архитектуры:

Укажите правильный вариант ответа:

Простота и скромность

Монументальность и многообразие декоративных элементов

Широкое использование западноевропейских форм и традиций

Торжественность и пышность

4. Put the words in the correct order to make sentences. 1. always/ shopping/ we/on /Tuesdays/go __________________________________________________ 2. usually/to/goes/the/in/park/evening/the/she _____________________________________________________ 3. never / Mark/paints/the/morning/in/ _____________________________________________________ 4. usually/I/breakfast/have/half/six/past/at _____________________________________________________ 5. we/visit/often/our/on /Sundays/granny ___________________________________________________

Презентация на тему: Введение в теорию графов

№ слайда 1

11 класс 11.02.2013 Введение в теорию графов

№ слайда 2

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

№ слайда 3

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

№ слайда 4

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

№ слайда 5

Нулевой граф Граф, состоящий из «изолированных» вершин, называется нулевым графом

№ слайда 6

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

№ слайда 7

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

№ слайда 8

Заметим, что если полный граф имеет n вершин, то количество ребер равно n(n-1)/2 Задание 1. Существует ли полный граф с семью ребрами? Решение: Зная количество ребер, узнаем количество вершин. n(n-1)/2=7. n(n-1)=14. Заметим, что n и (n-1) – это два последовательных натуральных числа. Число 14 нельзя представить в виде произведения двух последовательных натуральных чисел, значит, данное уравнение не имеет решений. Следовательно, такого графа не существует.

№ слайда 9

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

№ слайда 10

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

№ слайда 11

Ориентированный и неориентированный графы Рис. 5. Примеры неориентированного и ориентированного графов (А и Б)

№ слайда 12

Задание 3.Построить граф по заданному условию: В соревнованиях по футболу участвуют 6 команд. Каждую из команд обозначили буквами А, B, C, D, E и F. Через несколько недель некоторые из команд уже сыграли друг с другом: A с C, D, F;B c C, E, F;С с A, B;D с A, E, F;E с B, D, F;F с A, B, D.

№ слайда 13

Запомнить! Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет.

№ слайда 14

Изображение графа Один и тот же граф может выглядеть на рисунках по-разному. На рисунке 6 (а, б, в) изображен один и тот же граф. Рис. 6. Примеры изображения графа

№ слайда 15

Задание 4. Определить изображают ли фигуры на рисунке один и тот же граф или нет. Рисунок 1 и рисунок 2 являются изображениями одного графа. Рисунок 3 изображением другого графа

№ слайда 16

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

№ слайда 17

Задание 5. (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5). (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5). Определить какая из перечисленных последовательностей путём не является. Третья последовательность (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5).

№ слайда 18

Путь называется простым, если он не проходит ни через одну из вершин графа более одного раза. Задание 6. (А1 А4); (А4 А5). (А1 А2); (А2 А4); (А4 А5). (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5). (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5). Первая, вторая и четвертая последовательности являются путями, а третья нет, т.к. ребро (А1, А4) повторяется.Первая и вторая последовательность являются простыми путями, а четвертая нет, т.к. вершины А1 и А4 повторяются.

№ слайда 19

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

№ слайда 20

Задание 7. Назовите в графе циклы, содержащие a) 4 ребра; b) 6 ребер; c) 5 ребер; d) 10 ребер. Какие из этих циклов являются простыми?

№ слайда 21

ОТВЕТ Решение: (AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE) и т.д. – простые циклы. (DB, BE, EA, AB, BC, CD), (EC, CA, AB, BC, CD, DE) и т.д. – циклы. (AB, BC, CD, DE, EA), (AC, CE, EB, BD, DA) и т.д. – простые циклы. (AC, CE, EB, BD, DA, AB, BC, CD, DE, EA), (EB, BD, DA, AC, CE, EA, AB, BC, CD, DE) и т.д. – циклы.