4.Построение графов, матриц примыканий списка примыканий. Постройте графы соответствующие весовым матрицам


Построить граф по матрице

Построить ненаправленный граф по матрице

Заданная матрица смежности ненаправленного графа
Матрица смежности
Полученный граф, построенный по матрице
По матрице созданный граф

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г.

Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками.

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

Уже в XIX столетии графы использовались при построении схем электрических цепей и молекулярных схем.

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

В настоящее время теория графов находит многочисленные применения в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сеги нефтепроводов и вообще в так называемом «программировании». Теория графов теперь применяется и в таких областях, как экономика, психология и биология. 

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

Графы делятся на ненаправленные, направленные, с весовыми коэффицикентами(взвешенные) и без коэффициентов.

Каждый граф имеет определенные характеристики. Основные из них это остов графа, матрица смежности, матрица инцидентности.

Остов графа - это подграф данного графа, содержащий все его вершины и являющийся деревом.

Матрица смежности графа - это квадратная матрица ( по числу вершин графа) где, каждый элемент матрицы (на пересечении i- столбца и j-ряда) есть состояния связи  между вершинами i и j.

Элемент матрицы равен 1 если i-вершина графа, соединена с j-вершиной графа.

Во всех других случаях, в том числе когда i=j, значение элемента матрицы равно 0.

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

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

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

На этой странице  бот строит ненаправленный граф, если  для него задана  матрица смежности.

Если мы не можете в уме построить матрицу смежности, то для этого есть ресурс Теория графов. Матрица смежности онлайн где можно построить такую матрицу. 

Интересные особенности

В матрице смежности неориентированного графа (взвешенного или невзвешенного) не важно, есть одна очень важная особенность

Значения матрицы  относительно главной диагонали - одинаковы.

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

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

Примеры:

Задана матрица смежности такого вида

 

В запросе пишем  0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0

и получаем ответ

Заданная матрица смежности ненаправленного графа
Полученный граф, построенный по матрице
По матрице созданный граф

Матрица задана таким видом

Матрица смежности

Пишем в запросе 

0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0  0 1 0  0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0  1 0 0 0 0 1 0 0 0 1 0 0

получем ответ

Заданная матрица смежности ненаправленного графа
Полученный граф, построенный по матрице
По матрице созданный граф

 

Удачи в расчетах!!

 

  • Построить график функции c помощью GeoGebra >>

www.abakbot.ru

Инструмент для работы с графами онлайн

Задайте матрицу смежности. Используйте запятую "," в качестве разделителя

Мартрица имеет неправильный формат. Используйте запятую "," в качестве разделителя. Матрица должна иметь одинаковое количество столбцов и строк.

Задайте матрицу инцидентности. Используйте запятую "," в качестве разделителя

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

Ваш алгоритм отправлен на модерацию и в случае успеха он будет добавлен на сайт.

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

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

Задайте матрицу инцидентности. Используйте запятую "," в качестве разделителя

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

Выделите и перемещайте объекты или перемещайте рабочую область

Перемещайте курсор для перемещения объекта

Выделите и перемещайте объекты или перемещайте рабочую область

Перемещайте курсор для перемещения объекта

Кликните на рабочую область, чтобы добавить вершину. Нумерация вершин

Выделите первую вершину для создания дуги

Выделите вторую вершину, которую хотите соединить

Выделите вершину, из которой хотите найти кратчайших путь

Выделите конечную вершину кратчайшего пути

Расстояние между вершинами %d

Пути не существует

Кликните по объекту, который хотите удалить

Добавить ребро

Ориентированную

Неориентированную

Матрица смежности

Сохранить граф

Отмена

Мин. расстояние =

Матрица инцидентности

Сохранение графа

закрыть

Число компонентов связности графа равно

Число слабо связных компонентов равно

Что вы думаете о сайте?

Имя (email для ответа)

Написать

Отправить

Напишите нам

исправить матрицу

справка

Матрица имеет неправильный формат

Сохранение изображения графа

Полный отчёт

Краткий отчёт

Граф не содержит Эйлеров цикл

Граф содержит Эйлеров цикл

Обработка...

Добавить вершину

Переименовать вершину

Переименовать

ru

Изменить вес

ненагруженный

Групповое переименование

Опрос

Рекомендовать алгоритмы

Граф не содержит Эйлерову цепь

Граф содержит Эйлерову цепь

Граф минимальных расстояний.

Нажмите для сохранения

Показать матрицу расстояний

Матрица расстояний

Выделите исток максимального потока

Выделите сток максимального потока

Максимальный поток из %2 в %3 равен %1

Поток из %1 в %2 не существует

Исток

Сток

graphonline.ru

Самостоятельная работа по теме "Структура информации"

Просмотр содержимого документа «Самостоятельная работа по теме "Структура информации"»

10 класс

Самостоятельная работа по теме «Структура информации»

№1. Вычислите выражение, записанное в постфиксной форме:

а) 5 13 7 - *

б) 2 5 * 3 4 * +

в) a b c 7 + * -

при a = 28, b = 2 и c = 1.

№2. Вычислите выражение, записанное в префиксной форме:

а) * + 5 7 - 6 3

б) * - + a 3 b c

при a = 6, b = 4 и c = 2.

№3. Запишите выражение в постфискной форме:

(5-a)*(c-2*b)*d

№4. Выберите из списка структуры данных:

а) множество

б) числа

в) иерархия

г) графы

№5. Постройте матрицу смежности:

№6. Постройте весовую матрицу:

№7. Постройте графы, соответствующие каждой из весовых матриц:

№8. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M, N, Z. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Z?

№9. На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город M?

№10. Нарисуйте ориентированный граф:

multiurok.ru

Инцидентность и смежность в графах, матрицы смежности, матрицы инцидентности

Инцидентность - это когда вершина a является либо началом либо концом ребра e. Две вершины называются инцидентными, если у них есть общее ребро.

Для того, чтобы задать граф аналитически, множества V вершин графа и множества U рёбер графа, которые фигурировали в определении графа, будет недостаточно. Потребуется ещё и множество P троек вида (a, u, b), указывающих какую пару a, b элементов множества вершин V соединяет тот или иной элемент u множества рёбер U графа. Элементы множества P называются инциденциями графа. Вот мы и подошли к одному из первых понятий теории графов - инцидентности.

Понятие инцидентности - одно из главных при создании структур данных для представления графов в памяти ЭВМ, к которым мы перейдём после примера 1.

Пример 1. Задать аналитически граф, представленный на рисунке ниже. (рис. А)

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

Итак, задаём граф следующими множествами:

множество вершин: V = {a, b, c, d, e, f}

множество рёбер: U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

множество инциденций: P = {(b, 1, a), (b, 2, a), (a, 3, b), (b, 4, b), (b, 5, b), (c, 6, c), (c, 7, c), (b, 8, d), (d, 8, b), (b, 9, d), (b, 10, e), (b, 11, e), (e, 11, b)}

Смежность вершин графа - это когда две вершины графа соединены ребром.

Зададимся вопросом: можно ли поместить слона в компьютер? Ответ: можно, если слона смоделировать в виде графа, в котором вершинами являются части его тела, а рёбра соединяют те части тела, которые соединены в слоне как биологическом объекте. При этом получившийся граф должен быть представлен в памяти компьютера в понятном компьютеру виде.

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

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

Матрица смежности, как и матрица инцидентности, позволяет установить множество вершин, соседних с заданной (то есть рассматриваемой в конкретной задаче), не прибегая к полному просмотру всей матрицы. Матрицы смежности обычно представляются двумерным массивом размера n x n, где n - число вершин графа.

Матрица смежности S - это квадратная матрица, в которой и число строк, и число столбцов равно n - числу вершин графа. В ячейки матрицы смежности записываются некоторые числа в зависимости от того, соединены соответствующие вершины рёбрами или нет, и от типа графа.

Матрица смежности для неориентированного графа

Элемент матрицы смежности sij неориентированного графа определяется следующим образом:

- равен единице, если вершины vi и vj смежны;

- равен нулю, если вершины vi и vj не смежны.

Если для элемента матрицы vij имеет место i = j, то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.

Пример 2. Составить матрицу смежности для графа, представленного на рисунке ниже.

Ответ.

V12345
101100
210011
310001
401000
501100

Таким образом, матрица смежности неориентированного графа симметрична относительно главной диагонали.

Матрица смежности для ориентированного графа

Элемент матрицы смежности sij ориентированного графа определяется следующим образом:

- равен единице, если из вершины vi в вершину vj входит дуга;

- равен нулю, если из вершины vi в вершину vj дуга не входит.

Как и для неориентированных графов, так и для ориентированных, если для элемента матрицы vij имеет место i = j, то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.

Пример 3. Составить матрицу смежности для графа, представленного на рисунке ниже.

Ответ.

V12345
101000
201000
310000
401000
501100

Таким образом, матрица смежности ориентированного графа не симметрична.

Матрица смежности для графа с кратными рёбрами

Если в графе есть вершины, соединённые между собой несколькими рёбрами, то элемент матрицы смежности sij равен числу рёбер, соединяющих вершины vi и vj. Из этого следует, что если вершины vi и vj не соединены рёбрами, то элемент матрицы смежности sij равен нулю.

Пример 4. Составить матрицу смежности для графа, представленного на рисунке ниже.

Ответ.

V12345
103200
230011
320001
401000
501100

Матрица смежности для взвешенного графа

В случае взвешенного графа элемент матрицы смежности sij равен числу w, если существует ребро между вершинами vi и vj с весом w. Элемент sij равен нулю, если рёбер между вершинами vi и vj не существует.

Пример 5. Составить матрицу смежности для графа, представленного на рисунке ниже.

Ответ.

V12345
1011900
2110058
390002
405000
508200

Матрица инцидентности H - это матрица размера n x m, где n - число вершин графа, m - число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы - рёбрам графа.

Матрица инцидентности для неориентированного графа

Элемент матрицы инцидентности для неориентированного графа hij определяется следующим образом:

- равен единице, если вершина vi инцидентна ребру ej;

- равен нулю, если вершина vi не инцидентна ребру ej.

Пример 6. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

Ответ.

V1-21-32-42-53-5
111000
210110
301001
400100
500011

Матрица инцидентности для ориентированного графа

Элемент матрицы инцидентности для ориентированного графа hij определяется следующим образом:

- равен минус единице, если вершина vi является началом ребра ej;

- равен единице, если вершина vi является концом ребра ej;

- равен нулю, если вершина vi не инцидентна ребру ej.

Пример 7. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

Ответ.

V1-21-32-42-53-5
11-1000
2-10-1-10
30100-1
400100
500011

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

Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности.

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

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

Пример 8. Составить списки инцидентности для графа, представленного на рисунке ниже.

Ответ.

1:2→3 2:1→4→5 3:1→5 4:2 5:2→3

Матрицы смежности и инцидентности целесообразнее использовать когда:

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

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

Списки инцидентности целесообразнее использовать когда:

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

На практике списки чаще используются в прикладных целях.

Весь блок "Теория графов"

function-x.ru

Построение геометрических орграфов на основании матриц

Отношение x > y обладает следующими свойствами:

  1. Оно антирефлексивно, так как ни для каких х не имеет места x > x,  орграф отношения не имеет петель.
  2. Оно асимметрично, так как для двух чисел имеет место только соотношение x > y.
  3. Оно транзитивно, так как если x > y и y > z, то x > z, орграф отношения  является транзитивным, т.е. существуют замыкающие дуги:  и  влечет  и т.д.

Пример 5. Задана матрица

Нарисовать на плоскости орграф G = ( X, U ), единственный с точностью до изоморфизма, имеющий заданную матрицу В своей матрицей смежности. Найти матрицу инцидентности   орграфа G.

Решение. Заданная матрица смежности В имеет 4 строки и 4 столбца, следовательно, орграф имеет 4 вершины. Обозначим их соответственно ,, , . Матрицу В перепишем в виде

.

Построим на плоскости 4 точки и обозначим их ,, , .

Рис. 22. Изоморфный орграф G = ( X, U ).

Так как , то при вершине  нет петель, , значит из вершины  исходят 2 стрелки к вершине . Рассуждая таким же образом, построим геометрический орграф, изоморфный орграфу G = ( X, U ), для которого матрица В является матрицей смежности ( рис. 22 ).

Теперь запишем матрицу инцидентности С для орграфа G.

Построенный орграф G = ( X, U ) имеет 4 вершины и 12 дуг, т.е. Х={,,,},

U= .

Матрица инцидентности орграфа G будет иметь 4 строки и 12 столбцов

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

3. Задана симметрическая матрица А неотрицательных целых чисел.

    1. Нарисовать на плоскости граф (единственный с точностью до изоморфа), имеющий заданную матрицу А своей матрицей смежности. Найти матрицу инцидентности  графа G.

     2. Нарисовать на плоскости орграф  (единственный с точностью до изоморфизма), имеющий заданную матрицу А свое матрицей смежности. Найти матрицу инцидентности  орграфа G.

А=

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

=.

            Построим граф  по заданной матрице смежности.

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

А=

Рис. 3 Граф G=(X,U)

            Теперь найдем матрицу инцидентности графа G =(X,U).

Напомним определение матрицы инцидентности графа G=(X,U) с множеством вершин  и множеством ребер  Так называется матрица  размера , у которой

2. Заданная матрица А имеет 4 строки и 4 столбца, следовательно орграф имеет 4 вершины. Обозначим их соответственно   а матрицу представим в виде

 

            На плоскости строим 4 точки. Обозначим их через

                                                      Рис. 4. Изоморфный орграф G=(X,U).

            Так как   то при вершине   имеется петля;  значит, из вершины  выходят две стрелки к вершине  и т.д. (рис.4).

            Теперь запишем матрицу инцидентности С для орграфа G.

            Построим орграф G=(X,U) имеет 4 вершины и 17 дуг, т.е.

            Матрица инцидентности орграфа G будет иметь 4 строки и 17 столбцов

4. Заданная формула  От формулы  перейти к  эквивалентной ей формуле  так, чтобы формула  не содержала связок «» и «». Исходя из истинностных таблиц, доказать, что формулы  и  равно сильны (логически эквивалентны). Для формулы  СКНФ и СДНФ.

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

                                                   (1)

                                                         (2)

                                  (3)

               Используя равенства (1) – (3) и основные законы

21 – 30. Задана симметрическая матрица A неотрицательных целых чисел.

1. Нарисовать на плоскости граф G=(X,U)  (единственный с точностью до изоморфизма), имеющий заданную матрицу А своей матрицей смежности. Найти матрицу инцидентности  

графа G.

2. Нарисовать на плоскости орграф G=(X,U)  (единственный с точностью до изоморфизма)? Имеющий заданную матрицу А своей матрицей смежности. Найти матриц инцидентности

Орграфа G.

21.                                      22.

23.                                 24.         

25.                                        26.

27.                                                28.

29.                                                30.

vunivere.ru

4.Построение графов, матриц примыканий списка примыканий

Граф – множество вершин (узлов), соединенных ребрами (дугами). Обозначение графа:G=(V,E), гдеV– множество вершин,E– множество дуг.

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

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

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

Ячейка матрицы взвешенного графа содержит знак бесконечности ∞, если ребро отсутствует. Во всех остальных случаях значение ячейки равно весу.

Главная диагональ матрицы содержит нули.

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

Рисунок 8. Ориентированный граф.

Рисунок 9. Взвешенный граф. 21.09.12.

Рисунок 10. Взвешенный граф 5.10.12.

Список примыканий:

нулевая интенсивность на направлениях :1 4, 3 6, 5 4, потому что на данных участках дороги одностороннее движение;7 5 поворот запрещен на право.

Матрицы примыканий:

Московское шоссе х улица Ташкентская

Московское шоссе х улица Ташкентская 21.09.12.

Московское шоссе. х улица Ташкентская.5.10.12.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.

  1. Михеева, Т.И. Построение математических моделей объектов улично-дорожной сети города с использованием геоинформационных технологий // Информационные технологии. 2006. №1. С. 69-75.

  2. Михеева, Т.И., Михеев С.В. Модели наследования в системе управления дорожным движением // Информационные технологии. 2001. №7.С.50-54.

8

studfiles.net

Практическая работа № 1. Графы

Практическая работа № 1. Графы

1. Постройте матрицы смежности и весовые матрицы для каждого графа:

 

Матрицы смежности:

 

 

 

а)

б)

в)

г)

 

A

B

C

D

A

 

 

 

 

B

 

 

 

 

C

 

 

 

 

D

 

 

 

 

 

 

A

B

C

D

A

 

 

 

 

B

 

 

 

 

C

 

 

 

 

D

 

 

 

 

 

 

A

B

C

D

A

 

 

 

 

B

 

 

 

 

C

 

 

 

 

D

 

 

 

 

 

 

A

B

C

D

A

 

 

 

 

B

 

 

 

 

C

 

 

 

 

D

 

 

 

 

 

Весовые матрицы

 

 

 

а)

б)

в)

г)

 

A

B

C

D

A

 

 

 

 

B

 

 

 

 

C

 

 

 

 

D

 

 

 

 

 

 

A

B

C

D

A

 

 

 

 

B

 

 

 

 

C

 

 

 

 

D

 

 

 

 

 

 

A

B

C

D

A

 

 

 

 

B

 

 

 

 

C

 

 

 

 

D

 

 

 

 

 

 

A

B

C

D

A

 

 

 

 

B

 

 

 

 

C

 

 

 

 

D

 

 

 

 

 

2. Постройте графы, соответствующие каждой из матриц смежности:

а)

б)

в)

г)

 

A

B

C

D

Е

A

 

B

 

C

 

D

 

Е

 

 

 

A

B

C

D

Е

A

 

B

 

C

 

D

 

Е

 

 

 

A

B

C

D

Е

A

 

B

 

C

 

D

 

Е

 

 

 

A

B

C

D

Е

A

 

B

 

C

 

D

 

Е

 

 

а)

б)

в)

г)

           

 

3. Постройте графы, соответствующие каждой из весовых матриц:

а)

б)

в)

г)

 

A

B

C

D

Е

A

 

 

B

 

 

 

C

 

 

 

D

 

 

Е

 

 

 

 

 

A

B

C

D

Е

A

 

 

B

 

 

 

C

 

 

 

 

D

 

 

 

Е

 

 

 

 

 

A

B

C

D

Е

A

 

 

B

 

 

 

 

C

 

 

 

D

 

 

Е

 

 

 

 

 

 

A

B

C

D

Е

A

 

 

B

 

 

 

C

 

 

 

D

 

 

Е

 

 

 

 

а)

б)

в)

г)

           

 

Дата добавления: 2015-10-21; просмотров: 38 | Нарушение авторских прав

mybiblioteka.su - 2015-2018 год. (0.096 сек.)

mybiblioteka.su