Узел в графе называется вершиной (множественное число — вершины). Иногда его еще называют узлом; его также можно назвать точкой. Связь в графе называется ребром. Иногда это еще называют ссылкой; его также можно назвать линией.
- График с множеством функций
- Особенности графика
- Vertex
- Edge
- Цикл
- Край стрелки
- Инцидент
- Ненаправленный граф
- Направленный график
- Степень вершины
- Порядок графа
- Мультиграф
- Колчан
- Простой граф
- Пустой граф
- Смешанный граф
- Взвешенный график
- Indegree и Outdegree
- Программное представление графика
- Матрица смежности
- Ненаправленный граф и матрица смежности
- Направленный граф и матрица смежности
- Операции с графиком
- смежный (G, x, y)
- соседи (G, x)
- remove_vertex (G, x)
- add_vertex (G, x)
- add_edge (G, x, y)
- remove_edge (G, x, y)
- get_vertex_value (G, x)
- set_vertex_value (G, x, v)
- get_edge_value (G, x, y)
- set_edge_value (G, x, y, v)
- Заключение
- Об авторе
- Chrysanthus Forcha
График с множеством функций
На этом рисунке показан график с множеством функций:
Круги (диски) — это вершины. Любая прямая или изогнутая линия или петля является ребром.
Особенности графика
Vertex
Вершина — это объект. Это может быть дом; это может быть человек; это может быть абстрактное существительное; это может быть любой объект, о котором вы можете подумать.
Edge
Ребро — это соединение (отношение) между двумя вершинами; соединение может быть абстрактным.
Цикл
Цикл — это ребро, которое соединяет вершину с самим собой.
Край стрелки
Рассмотрим двух людей: Джона и Питера. Если Джон ссужает Питеру 100 долларов, и если Джон и Питер являются вершинами, то кредитное ребро будет направлено в сторону Питера. Если оба партнера забывают, что Питер должен Джону, а Питер ссужает Джону 100 долларов, то на другом конце того же края стрелка будет указывать на Джона. Если бы Петр одолжил Джону только 75 долларов, а не 100, тогда другое преимущество связывало бы Петра с Иоанном. У этого второго края будет стрелка, указывающая на Джона. Во втором случае есть два ребра, каждое с одной стрелкой, указывающее в противоположных направлениях.
Вершина, на которую указывает ребро, является головной вершиной этого ребра. Вершина, из которой выходит ребро, является вершиной хвоста.
Инцидент
Ребро соединяет две вершины. Ребро инцидентно любой вершине. На краю не обязательно должна быть стрелка. Две вершины называются концами ребра. Возможно иметь граф, вершина которого не принадлежит ни одному ребру, но это не будет рассматриваться в этом руководстве.
Ненаправленный граф
Ребро может быть стрелой, иначе не может. Граф, в котором нет ребра в виде стрелки, является неориентированным графом. Ребро может быть представлено прямой линией, кривой или петлей.
Направленный график
График, в котором каждое ребро представляет собой стрелку (направление), является направленным график. Край стрелки может быть представлен прямой линией со стрелкой, кривой со стрелкой или петлей с острием стрелки..
Отсутствие направления на краю неориентированного графа означает, что каждое ребро неориентированного графа является двунаправленным.
Степень вершины
Количество ребер, инцидентных вершине, — это степень вершины. Цикл имеет две вхождения в вершину, поэтому цикл учитывается дважды.
Порядок графа
Порядок графа — это количество вершин в граф.
Мультиграф
Мультиграф — это граф, в котором для некоторых пар вершин имеется более одного ребра. Неориентированный мультиграф — это такой граф, в котором ребра не имеют направлений (не являются стрелками). Направленный мультиграф — это такой, в котором каждое ребро представляет собой стрелку, а для пар вершин, имеющих более одной стрелки, одна вершина является хвостом этих стрелок, а другая вершина — головкой этих стрелок. На следующей схеме показан неориентированный мультиграф:
Более одного ребра (т. е. несколько ребер) для пары вершин также называются параллельными ребрами.
Колчан
Колчан — это мультиграф, который допускает циклы (один или несколько циклов) . Некоторые мультиграфы не допускают циклов.
Простой граф
Простой граф — это граф, в котором никакие две пары вершин не имеют нескольких ребер. Циклы не допускаются в простом графе.
Пустой граф
Пустой граф — это граф без вершин и, следовательно, без ребер.
Смешанный граф
Смешанный граф — это граф, в котором одни ребра являются стрелками, а другие — нет; другими словами: одни ребра имеют направления, а другие — нет.
Взвешенный график
Можно иметь граф, в котором число, известное как вес , назначается каждому ребру. Некоторые ребра имеют одинаковые номера, но, как правило, номера разные. Такой граф называется взвешенным графом. Числа для конкретного графика могут представлять длину или стоимость (цены) или величину какого-либо вида, в зависимости от проблемы.
Indegree и Outdegree
Словарь, степень , и outdegree применимы только к ориентированному графу. Граф может быть мультиграфом, а может и не быть. Граф может иметь петли, а может и не иметь.
Количество стрелок, соединенных с вершиной, является степенью этой вершины. Стрела с одинарным наконечником имеет острие и конец. Количество хвостов, соединенных с вершиной, является исходной степенью этой вершины.
Примечание: граф с несколькими ребрами для пары вершин, где несколько ребер находятся в противоположных направлениях, не рассматривается в это руководство.
Программное представление графика
Программно граф можно представить так, как он нарисован на диаграмме. Граф также может быть представлен в программном обеспечении математической матрицей (двумерным массивом). Одна из таких матриц называется матрицей смежности.
Матрица смежности
Матрица смежности — это квадратная матрица. Заголовки строк — это все вершины, записанные в порядке возрастания.. Заголовки столбцов — все те же вершины, записанные в порядке возрастания. Подсчет строк или столбцов матрицы начинается с 1, а не с нуля, как в случае с массивами. При идентификации элемента в матрице номер строки записывается первым перед номером столбца.
Для неориентированного графа каждая запись (элемент) в матрице смежности — это количество ребер, соединяющих два соответствующие вершины. Петлю следует пересчитать дважды. Для ориентированного графа каждая запись в матрице смежности — это либо количество ребер, выходящих из вершины строки и входящих в соответствующую вершину столбца, либо количество ребер, выходящих из вершины столбца и входящих в соответствующую вершину строки. Выбор остается за программистом. В этой ситуации (в любом случае) цикл все равно следует подсчитывать один раз.
Примечание. График — это диаграмма, которая сама по себе является структурой данных. Матрица смежности также является самостоятельной структурой данных.
Ненаправленный граф и матрица смежности
На следующих диаграммах показан неориентированный граф и соответствующая матрица смежности:
Ведущая диагональ матрицы — это диагональ от верхнего левого угла до нижнего правого. Ненаправленная матрица симметрична относительно ведущей диагонали. Матричный элемент для строки A и столбца C равен 1, что означает, что есть одно ребро, соединяющее вершину A и вершину C. Матричный элемент для строки C и столбца B равен 3, что означает, что есть 3 ребра, соединяющие вершину C и вершину B. другие записи объясняются аналогично.
Сумма записей для строки дает количество ребер (степень) для соответствующей вершины. Сумма записей для строки A равна 2, что означает, что 2 ребра соединены с вершиной A. Сумма записей для строки B равна 6, что означает, что 6 ребер соединены с вершиной B. Остальные элементы объясняются аналогичным образом.
Направленный граф и матрица смежности
На следующих диаграммах показан ориентированный граф и соответствующая матрица смежности:
Матрица смежности для ориентированного графа не обязательно симметрична относительно главной диагонали. Элемент матрицы для строки A и столбца C равен 1, что означает, что одно ребро уходит из вершины A в вершину C. Матричный элемент для строки C и столбца B равен 3, что означает, что 3 ребра уходят из вершины C в вершину B. объясняются аналогичным образом.
Сумма записей для столбца дает степень для вершины (столбца). Сумма записей для строки дает исходящую степень для вершины (строки). Сумма записей для столбца A равна 1, что означает, что одно ребро направлено в вершину A. Сумма записей для строки B равна 2, что означает, что 2 ребра выходят из вершины B. Остальные элементы объясняются аналогичным образом..
Операции с графиком
Структура данных, такая как график, состоит из набора значений данных или набора объектов, а также взаимосвязи между объектами и операции (функции) между объектами. Отношения в графе обозначены ребрами. При этом граф должен иметь как минимум следующие операции:
смежный (G, x, y)
G означает граф. Эта операция проверяет, соединяет ли ребро вершину x и вершину y. Значение и позиция записи в матрице указывают соединение ребра (и его тип).
соседи (G, x)
Эта операция возвращает список всех вершин, которые напрямую связаны с вершиной x. Значение и позиция записи в матрице указывают на соединение ребра.
remove_vertex (G, x)
Эта операция удаляет вершину x из график. Если у вершины нет ребра, это не проблема. Однако, если в вершине были связи, то связи (ребра) также следует удалить. Значение и позиция записи в матрице указывают на наличие конкретной вершины. Если вершина удаляется, матрица должна быть скорректирована.
add_vertex (G, x)
Это добавляет вершину x без добавления ребер или заменяет вершина, которая имела ребра, но была удалена. Значение и позиция записи в матрице указывают на наличие конкретной вершины. Если добавляется вершина, матрица должна быть скорректирована.
add_edge (G, x, y)
Эта операция добавляет новое ребро между вершиной x и вершина y, если ребра там не было. Значение и позиция записи в матрице указывают на наличие определенного края. Если добавлено ребро, матрицу необходимо перенастроить.
remove_edge (G, x, y)
Эта операция удалит ребро между вершиной x и вершина y, если ребро было там. Значение и позиция записи в матрице указывают на наличие определенного края. Если ребро удалено, матрицу необходимо перенастроить.
get_vertex_value (G, x)
Эта операция возвращает значение v, связанное с вершиной, x . Для этого вам понадобится мощный набор подмножеств для меток вершин и их значений.
set_vertex_value (G, x, v)
Эта операция дает новое значение , v для значения, связанного с вершиной, x. Для этого вам понадобится мощный набор подмножеств для меток вершин и их значений.
Некоторые графы также связывают значения со своими ребрами. Такие графы требуют следующих дополнительных операций:
get_edge_value (G, x, y)
Эта операция возвращает значение v, связанное с ребром, (x, y ). Для этого вам понадобится мощный набор подмножеств для ребер и их значений.
set_edge_value (G, x, y, v)
Эта операция дает новый value, v для значения, связанного с ребром, (x, y). Для этого вам понадобится мощный набор подмножеств для ребер и их значений.
Заключение
Граф — это набор вершин, соединенных ребрами. Граф может быть неориентированным или направленным. Края могут быть ненаправленными или направленными. Петли могут присутствовать или отсутствовать на графике. Далее вам следует изучить набор, набор мощности и мультимножество, относящиеся к графам. После этого вы должны изучить различные типы графов, такие как ориентированный граф, регулярный граф, полный граф, двудольный граф, турнирный граф, потоковый сетевой граф и т. Д.
Chrys
Об авторе
Chrysanthus Forcha
Первооткрыватель математической интеграции из первых принципов и связанных серий. Степень магистра технического образования по специальности «Электроника и компьютерное программное обеспечение». Бакалавр электроники. У меня также есть знания и опыт на уровне магистра в области вычислительной техники и телекоммуникаций. Из 20 000 писателей я был 37-м лучшим писателем на сайте devarticles.com. Я работаю в этих областях более 10 лет.
