Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор
В этой статье:
Матрица смежности
Матрица инцидентности
Список смежности (инцидентности)
Взвешенный граф (коротко)
Итак, мы умеем задавать граф графическим способом. Но есть еще два способа как можно задавать граф, а точнее представлять его. Для экономии памяти в компьютере граф можно представлять с помощью матриц или с помощью списков.
Матрица является удобной для представления плотных графов, в которых число ребер близко к максимально возможному числу ребер (у полного графа).
Другой способ называется списком. Данный способ больше подходит для более разреженных графов, в котором число ребер намного меньше максимально возможного числа ребер (у полного графа).
Перед чтением материала рекомендуется ознакомится с предыдущей статьей, о смежности и инцидентности, где данные определения подробно разбираются.
Матрица смежности
Но тем кто знает, но чуть забыл, что такое смежность есть краткое определение.
Смежность – понятие, используемое только в отношении двух ребер или в отношении двух вершин: два ребра инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Матрица (назовем ее L) состоит из n строк и n столбцов и поэтому занимает n^2 места.
Каждая ячейка матрицы равна либо 1, либо 0;
Ячейка в позиции L (i, j) равна 1 тогда и только тогда, когда существует ребро (E) между вершинами (V) i и j. Если у нас положение (j, i), то мы также сможем использовать данное правило. Из этого следует, что число единиц в матрице равно удвоенному числу ребер в графе. (если граф неориентированный). Если ребра между вершинами i и j не существует, то ставится 0.
Для практического примера возьмем самый обыкновенный неориентированный граф:
А теперь представим его в виде матрицы:
Ячейки, расположенные на главной диагонали всегда равны нулю, потому что ни у одной вершины нет ребра, которое и начинается, и заканчивается в ней только если мы не используем петли. То есть наша матрица симметрична относительно главной диагонали. Благодаря этому мы можем уменьшить объем памяти, который нам нужен для хранения.
С одной стороны объем памяти будет:
Но используя вышеописанный подход получается:
Потому что нижнюю часть матрицы мы можем создать из верхней половины матрицы. Только при условии того, что у нас главная диагональ должна быть пустой, потому что при наличии петель данное правило не работает.
Если граф неориентированный, то, когда мы просуммируем строку или столбец мы узнаем степень рассматриваемой нами вершины.
Если мы используем ориентированный граф, то кое-что меняется.
Здесь отсутствует дублирование между вершинами, так как если вершина 1 соединена с вершиной 2, наоборот соединена она не может быть, так у нас есть направление у ребра.
Возьмем в этот раз ориентированный граф и сделаем матрицу смежности для него:
В виде матрицы:
Если мы работаем со строкой матрицы, то мы имеем элемент из которого выходит ребро, в нашем случаи вершина 1 входит в вершину 2 и 8. Когда мы работаем со столбцом то мы рассматриваем те ребра, которые входят в данную вершину. В вершину 1 ничего не входит, значит матрица верна.
Объем памяти:
Если бы на главной диагонали была бы 1, то есть в графе присутствовала петля, то мы бы работали уже не с простым графом, с каким мы работали до сих пор.
Используя петли мы должны запомнить, что в неориентированном графе петля учитывается дважды, а в ориентированном — единожды.
Матрица инцидентности
Инцидентность – понятие, используемое только в отношении ребра и вершины: две вершины (или два ребра) инцидентными быть не могут.
Матрица (назовем ее I) состоит из n строк которое равно числу вершин графа, и m столбцов, которое равно числу ребер. Таким образом полная матрица имеет размерность n x m. То есть она может быть, как квадратной, так и отличной от нее.
Ячейка в позиции I (i, j) равна 1 тогда, когда вершина инцидентна ребру иначе мы записываем в ячейку 0, такой вариант представления верен для неориентированного графа.
Сразу же иллюстрируем данное правило:
В виде матрицы:
Сумма элементов i-ой строки равна степени вершины.
При ориентированным графе, ячейка I (i, j) равна 1, если вершина V (i) начало дуги E(j) и ячейка I (i, j) равна -1 если вершина V (i) конец дуги E (j), иначе ставится 0.
Ориентированный граф:
В виде матрицы:
Одной из особенностей данной матрицы является то, что в столбце может быть только две ненулевых ячейки. Так как у ребра два конца.
При суммировании строки, ячейки со значением -1, могут складываться только с ячейками, также имеющими значение -1, то же касается и 1, мы можем узнать степень входа и степень выхода из вершины. Допустим при сложении первой вершины, мы узнаем, что из нее исходит 1 ребро и входят два других ребра. Это является еще одной особенностью (при том очень удобной) данной матрицы.
Объем памяти:
Список смежности (инцидентности)
Список смежности подразумевает под собой, то что мы работаем с некоторым списком (массивом). В нем указаны вершины нашего графа. И каждый из них имеет ссылку на смежные с ним вершины.
В виде списка это будет выглядеть так:
Неважно в каком порядке вы расположите ссылку так как вы рассматриваете смежность относительно первой ячейки, все остальные ссылки указывают лишь на связь с ней, а не между собой.
Так как здесь рассматривается смежность, то здесь не обойдется без дублирования вершин. Поэтому сумма длин всех списков считается как:
Объем памяти:
Когда мы работаем с ориентированным графом, то замечаем, что объем задействованной памяти будет меньше, чем при неориентированном (из-за отсутствия дублирования).
В виде списка:
Сумма длин всех списков:
Объем памяти:
Со списком инцидентности все просто. Вместо вершин в список (массив) вы вставляете рёбра и потом делаете ссылки на те вершины, с которыми он связан.
К недостатку списка смежности (инцидентности) относится то что сложно определить наличие конкретного ребра (требуется поиск по списку). А если у вас большой список, то удачи вам и творческих успехов! Поэтому, чтобы работать максимальной отдачей в графе должно быть мало рёбер.
Взвешенность графа
Взвешенный граф — это граф, в котором вместо 1 обозначающее наличие связи между вершинами или связи между вершиной и ребром, хранится вес ребра, то есть определённое число с которым мы будем проводить различные действия.
К примеру, возьмем граф с весами на ребрах:
И сделаем матрицу смежности:
В ячейках просто указываем веса ребра, а в местах где отсутствует связь пишем 0 или -∞.
Более подробно данное определение будет рассмотрено при нахождении поиска кратчайшего пути в графе.
Итак, мы завершили разбор представления графа с помощью матрицы смежности и инцидентности и списка смежности (инцидентности). Это самые известные способы представления графа. В дальнейшем мы будем рассматривать и другие матрицы, и списки, которые в свою очередь будут удобны для представления графа с определёнными особенностями.
Если заметили ошибку или есть предложения пишите в комментарии.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
На каком языке программирования проводить операции с графами
21.28%
Использовать оба
10
Проголосовали 47 пользователей.
Воздержались 8 пользователей.
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Prerequisite: Graph and its representations
Given a adjacency matrix representation of a Graph. The task is to convert the given Adjacency Matrix to Adjacency List representation.
Examples:
Input: arr[][] = [ [0, 0, 1], [0, 0, 1], [1, 1, 0] ]
Output: The adjacency list is:
0 -> 2
1 -> 2
2 -> 0 -> 1
Input: arr[][] = [ [0, 1, 0, 0, 1], [1, 0, 1, 1, 1], [0, 1, 0, 1, 0], [0, 1, 1, 0, 1], [1, 1, 0, 1, 0] ]
Output: The adjacency list is:
0 -> 1 -> 4
1 -> 0 -> 2 -> 3 -> 4
2 -> 1 -> 3
3 -> 1 -> 2 -> 4
4 -> 0 -> 1 -> 3
Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.
Adjacency List: An array of lists is used. The size of the array is equal to the number of vertices. Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex.
To convert an adjacency matrix to the adjacency list. Create an array of lists and traverse the adjacency matrix. If for any cell (i, j) in the matrix “mat[i][j] != 0“, it means there is an edge from i to j, so insert j in the list at i-th position in the array of lists.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> convert( vector<vector<int>> a)
{
vector<vector<int>> adjList(a.size());
for (int i = 0; i < a.size(); i++)
{
for (int j = 0; j < a[i].size(); j++)
{
if (a[i][j] != 0)
{
adjList[i].push_back(j);
}
}
}
return adjList;
}
int main()
{
vector<vector<int>> a;
vector<int> p({0, 0, 1});
vector<int> q({0, 0, 1});
vector<int> r({1, 1, 0});
a.push_back(p);
a.push_back(q);
a.push_back(r);
vector<vector<int>> AdjList = convert(a);
cout<<"Adjacency List:"<<endl;
for (int i = 0; i < AdjList.size(); i++)
{
cout << i;
for(int j = 0; j < AdjList[i].size(); j++)
{
if(j == AdjList[i].size() - 1)
{
cout << " -> " << AdjList[i][j] << endl;
break;
}
else
cout << " -> " << AdjList[i][j];
}
}
}
Java
import java.util.*;
public class GFG {
static ArrayList<ArrayList<Integer>> convert(int[][] a)
{
int l = a[0].length;
ArrayList<ArrayList<Integer>> adjListArray
= new ArrayList<ArrayList<Integer>>(l);
for (int i = 0; i < l; i++) {
adjListArray.add(new ArrayList<Integer>());
}
int i, j;
for (i = 0; i < a[0].length; i++) {
for (j = 0; j < a.length; j++) {
if (a[i][j] != 0) {
adjListArray.get(i).add(j);
}
}
}
return adjListArray;
}
static void printArrayList(ArrayList<ArrayList<Integer>>
adjListArray)
{
for (int v = 0; v < adjListArray.size(); v++) {
System.out.print(v);
for (Integer u : adjListArray.get(v)) {
System.out.print(" -> " + u);
}
System.out.println();
}
}
public static void main(String[] args)
{
int[][] a = { { 0, 0, 1 },
{ 0, 0, 1 },
{ 1, 1, 0 } };
ArrayList<ArrayList<Integer>> adjListArray = convert(a);
System.out.println("Adjacency List: ");
printArrayList(adjListArray);
}
}
Python3
from collections import defaultdict
def convert(a):
adjList = defaultdict(list)
for i in range(len(a)):
for j in range(len(a[i])):
if a[i][j] != 0:
adjList[i].append(j)
return adjList
a =[[0, 0, 1], [0, 0, 1], [1, 1, 0]]
AdjList = convert(a)
print("Adjacency List:")
for i in AdjList:
print(i, end ="")
for j in AdjList[i]:
print(" -> {}".format(j), end ="")
print()
C#
using System;
using System.Collections.Generic;
class GFG
{
static List<List<int>> convert(int[,] a)
{
int l = a.GetLength(0);
List<List<int>> adjListArray = new List<List<int>>(l);
int i, j;
for (i = 0; i < l; i++)
{
adjListArray.Add(new List<int>());
}
for (i = 0; i < a.GetLength(0); i++)
{
for (j = 0; j < a.GetLength(1); j++)
{
if (a[i,j] != 0)
{
adjListArray[i].Add(j);
}
}
}
return adjListArray;
}
static void printList(List<List<int>> adjListArray)
{
for (int v = 0; v < adjListArray.Count; v++)
{
Console.Write(v);
foreach (int u in adjListArray[v])
{
Console.Write(" -> " + u);
}
Console.WriteLine();
}
}
public static void Main(String[] args)
{
int[,] a = { { 0, 0, 1 }, { 0, 0, 1 }, { 1, 1, 0 } };
List<List<int>> adjListArray = convert(a);
Console.WriteLine("Adjacency List: ");
printList(adjListArray);
}
}
Javascript
function convert(a) {
let adjList = new Array(a.length);
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < a[i].length; j++) {
if (a[i][j] != 0) {
if (!adjList[i]) {
adjList[i] = [];
}
adjList[i].push(j);
}
}
}
return adjList;
}
let a = [[0, 0, 1], [0, 0, 1], [1, 1, 0]];
let AdjList = convert(a);
console.log("Adjacency List:");
for (let i = 0; i < AdjList.length; i++) {
let output = i;
for (let j = 0; j < AdjList[i].length; j++) {
if (j === AdjList[i].length - 1) {
output += " -> " + AdjList[i][j];
break;
} else {
output += " -> " + AdjList[i][j];
}
}
console.log(output);
}
Output
Adjacency List: 0 -> 2 1 -> 2 2 -> 0 -> 1
Time Complexity: O(N2).
Auxiliary Space: O(N2).
Last Updated :
20 Feb, 2023
Like Article
Save Article
В чем особенности представления графа матрицей смежности
Содержание:
-
Матрица смежности для графов
- В чем особенности представления
- Списки смежности и списки ребер, плюсы и минусы
- Классификация графов
- Способы представления графа, алгоритмы обхода
- Как построить граф по матрице смежности
Матрица смежности для графов
Матрица смежности графа является квадратной матрицей с элементами, каждый из которых имеет одно из двух значений: 0 или 1.
Простой пример матрицы смежности изображен на рисунке.
Данная матрица является двоичной квадратной, то есть количество строк в единичном случае соответствует количеству столбцов, а также строки и столбы имеют значения либо 1, либо 0. Первая строка и первый столбец, не состоящие в матрице, а записанные для легкости восприятия, содержат номера, на пересечении которых расположен каждый из элементов, и они определяют индексное значение последних. Достаточно просто выполнить построение матрицы данного типа, зная соответствующий ей граф.
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
В левой стороне на рисунке представлена аналогичная матрица смежности с размерностью 4х4. Числа, выделенные синим цветом, допустимо рассматривать в виде вершин смешанного графа, записанного в правой стороне – того, представлением которого является матрица.
Отобразить граф можно путем вычисления по матрице смежности числа его вершин и применения специального правила. В том случае, когда из одной вершины в другую проход свободен, то есть имеется ребро, в ячейку записывают 1, в противном случае – 0. Таким образом:
если из i в j существует ребро, то (A[i][j]:=1), в противном случае (A[i][j]:=0.)
Заметим, что для элементов, расположенных на главной диагонали, характерно нулевое значение. Это является следствием отсутствия у графа петель. Однако, в информатике нет ограничений для записи некоторых или всех элементов на главной диагонали в виде единиц.
В чем особенности представления
В программе матрицу смежности задают с помощью обычного двумерного массива. Его размерность соответствует n x n, где n является числом вершин графа.
В том случае, когда граф неизвестен заранее, а определен пользователем, необходимо вводить двумерный массив вручную. Это объясняется условиями работы конкретного языка программирования. При необходимости предоставления графа в виде матрицы смежности требуется (O(|V|^{2})) памяти, так как ее размер соответствует квадрату числа всех вершин.
Если количество ребер графа в сравнении с числом вершин является небольшим, значения многих элементов матрицы смежности будут соответствовать нулю. Таким образом, применение рассматриваемой методики нецелесообразно, в связи с наличием для подобных графов наиболее эффективных способов представления.
Списки смежности и списки ребер, плюсы и минусы
Относительно памяти, списки смежности менее требовательны по сравнению с матрицами смежности. Объем памяти для их хранения составляет (O(|V|+|E|)). Такой перечень целесообразно представить как таблицу с двумя столбцами и строками в количестве, не превышающем число вершин в графе. Для примера можно рассмотреть граф смешанного типа:
В данном случае, граф состоит из 6 вершин (|V|) и 5 ребер (|E|). Из последних 2 ребра являются направленными и 3 ненаправленными. При этом из каждой вершины выходит, как минимум одно ребро в другую вершину. Таким образом, список смежности рассматриваемого графа содержит |V| строк.
В i строке и 1 столбце указана вершина выхода, а в i строке и 2 столбце – вершина входа. Например, из вершины 5 выходят два ребра, входящие в вершины 1 и 4.
В процессе программной реализации списка смежности число вершин и ребер задают с помощью клавиатуры. Можно установить лимиты, то есть задать пару констант, одна из которых определяет максимально допустимое число вершин (Vmax), другая – ребер (Emax). Затем следует использовать три одномерных целочисленных массива:
- terminal[1..Emax] – для хранения вершин, содержащих ребра;
- next [1..Emax] – включает указатели на элементы массива terminal;
- head[1..Vmax] – состоит из указателей на начало подсписков, то есть такие вершины, записанные в массив terminal, с которых начинается процесс перечисления всех вершин, смежных одной i-ой вершине.
Примечание
Допустимым действием является выделение в программе двух ключевых частей. К ним относят ввод ребер для дальнейшего добавления их в список смежности и вывод полученного списка смежности на экран.
В первую очередь выполняют запрос на ввод суммы вершин (n) и ребер (m) графа (данная информация должна быть у пользователя). Следующим шагом является запуск цикла ввода ребер, то есть смежных вершин. Условие в этом цикле нужно для того, чтобы узнать, какое введено ребро.
Если введено направленное ребро, то функция add вызывается 1 раз, иначе – 2, тем самым внося сведения, что есть ребро как из вершины v в вершину u, так и из u в v. По окончанию формирования списка смежности происходит его отображение программой на экране.
Вывод на экран осуществляется:
- по циклу от 1 до n, где n – является количеством вершин;
- согласно вложенному в него циклу, который прекращает свою работу тогда, когда указатель на следующий элемент для i-ой вершины отсутствует, то есть все смежные ей вершины уже выведены.
Функция add производит добавление ребер в изначально пустой список смежности:
(Add(v, u))
(k:=k+1)
(terminal[k]:=u)
(next[k]:=head[v])
(head[v]:=k)
Действия реализуются, согласно алгоритму с формальными параметрами, вспомогательной переменной k и тремя одномерными целочисленными массивами:
- значение переменной k увеличивается на 1;
- в k-ый элемент массива terminal добавляют конечную для какого-либо ребра вершина (u);
- в строке №3 для k-ого элемента массива next определяется адрес следующего элемента массива terminal;
- массив head заполняют указателями на стартовые элементы, которые являются началом подсписка (строки в таблице) смежных вершин с некоторой i-ой вершиной.
В ячейке, где пересекаются i-ая строка и 2-ой столбец, могут быть записи нескольких элементов в соответствии с несколькими смежными вершинами. Можно обозначить каждую строку из списка смежности его подсписком. В результате выведенный список смежности будет включать элементы подсписков, отсортированные в обратном порядке. Обычно порядок вывода смежных вершин (в подсписках) не имеет принципиального значения.
Список со строками, содержащими запись двух смежных вершин и вес ребра, которое их соединяет, называют списком ребер графа. В качестве примера можно рассмотреть связный граф G=(V, E). Множество ребер E следует сгруппировать следующим образом:
- d – подмножество, включающее только неориентированные ребра графа G;
- k – подмножество, включающее только ориентированные ребра графа G.
Допустим, какая-либо величина p равна количеству всех ребер, которые включены в подмножество d, а s – то же самое относительно k. Тогда для графа G высотой списка ребер будет являться величина:
s+p*2
Таким образом, число строк из списка ребер в любом случае должно соответствовать величине, определенной по итогам сложения ориентированных ребер с неориентированными, умноженными на 2. Рассматриваемый способ представления графа предполагает хранение в каждой строке пары смежных вершин, а неориентированное ребро, которое соединяет вершины v и u, идет как из v в u, так и из u в v.
Например, имеется некий граф смешанного типа с 5 вершинами и 4 ребрами, каждому из которых соответствует определенное целое значение (для наглядности оно составлено из номеров вершин):
Граф содержит 3 направленных ребра и 1 ненаправленное. Путем подстановки значений в формулу можно определить высоту списка ребер: 3+1*2=5
На рисунке изображен список ребер для рассматриваемого графа. Таблица в размерах составляет n×3, где n= s+p*2=3+1*2=5. Элементы в первом столбце расположены по возрастанию, во втором – порядок расположения элементов определен первым, а в третьем – зависит от двух предыдущих.
Список ребер реализуется программой. Процесс схож с операциями при реализации списка смежностей. В первую очередь организуют ввод данных, которые с помощью особой функции распределяются среди массивов. Затем происходит вывод полученного списка смежности на экран. В связи с необходимостью в использовании дополнительного массива, функция добавления ребер организована по-другому.
Максимально допустимое число вершин в графе определено с помощью константы Vmax, а количество ребер – Emax. Вторая константа инициализируется формулой Vmax*(Vmax-1)/2, вычисляющей количество ребер в полном графе при известном числе вершин.
Далее, в программах описываются 5 массивов:
- terminal – массив вершин, включающий ребра;
- weight – массив весов ребер;
- head[i]=k – для хранения i-ой вершины номер k-ого элемента массивов terminal и weight, где terminal[k] – является первой вершиной, смежной с i-ой, а weight[k] – вес инцидентного ей ребра;
- last[i]=k – для хранения i-ой вершины номер k-ого элемента массивов terminal и weight, где terminal[k] – является последней вершиной, смежной с i-ой, а weight[k] – вес инцидентного ей ребра;
- point[i]=k – хранит для i-ой вершины номер k-ого элемента массивов terminal и weight, где terminal[k] – следующая вершина, смежная с i-ой, а weight[k] – вес инцидентного ей ребра.
По результатам ввода числа вершин (n) и ребер (m) графа будет запущен цикл, каждый этап которого сопровождается вводом пользователем с клавиатуры пары смежных вершин и веса ребра, расположенного между ними. Если ребро ориентированное, функция записи в список ребер (Add) вызывается единожды, при неориентированном ребре – дважды. Суммарное количество вызовов функции определяется по формуле:
s+(p*2)
где s – является ориентированными ребрами графа
p – неориентированные ребра
По итогам формирования списка ребер следует умножить на 2 переменную m. Это связано с тем, что при чисто неориентированном графе высота списка составляет:
0+(m*2)
Завершающим этапом является отображение на экране результирующей конструкции. В связи с тем, что на номер первой вершины, смежной с i-ой вершиной, указывает элемент head[i], каждая новая итерация внешнего цикла начинается с взятия этого номера (k=head[i]). Внутренний цикл прекращает реализацию в том случае, когда отсутствует смежная с i-ой вершины (k станет равной нулю), а внешний – по окончанию вывода списка ребер.
Ключевые действия, включая добавление ребра, удаление ребра, проверку наличия ребра от вершины i до вершины j, отличаются высокой эффективностью и являются операциями с постоянным временем. В том случае, когда граф плотный, а количество ребер большое, матрица смежности представляет собой наиболее целесообразное решение. Даже когда граф и матрица смежности разрежены, можно представить ее с помощью структур данных для разреженной матрицы.
Главное достоинство методики заключается в применении матриц. Благодаря передовым разработкам в сфере аппаратного обеспечения, представляется возможным реализовывать даже дорогостоящие матричные операции на графическом процессоре (GPU). В процессе выполнения операций со смежной матрицей можно получить ценные данные о природе графа и том, как связаны его вершины.
К минусам матрицы смежности можно отнести риски возникновения недостатка объема памяти по причине наличия требований к пространству матрицы смежности VxV. Однако, зачастую графы не обладают чрезмерно большим числом соединений, что является основным поводом выбрать списки смежности для решения распространенных задач.
С другой стороны, несмотря на простоту базовых операций, существуют такие операции, как inEdges и outEdges, которые отличаются дороговизной при использовании для представления матрицы смежности.
Классификация графов
Ярким примером графа является схема метро или некий другой маршрут. Программисты знакомы с компьютерной сетью, которая также представляет собой граф. Общим в этих примерах является наличие точек, соединенных линиями.
В случае компьютерной сети точками являются отдельные серверы, а линиями – разные типы электрических сигналов. В метрополитене точки можно принять за станции, а линии – за туннели, проложенные между станциями. Согласно теории графов, точки представляют собой вершины или узлы, а линии – ребра или дуги.
Граф является совокупностью вершин, которые соединены ребрами.
В математике преимущественно рассматривают не содержание, а структуру вещей, отделяя ее от всего остального. Данный прием позволяет определять какие-либо объекты, как графы. В случае компьютерной сети можно отметить наличие определенной топологии и возможности условного представления в виде некоторого количества компьютеров и соединительных путей. На рисунке изображена полносвязная топология:
Фактически такая топология является графом. Пять компьютеров представляют собой вершины, а соединения или пути передачи сигналов являются ребрами. Ели выполнить замену компьютеров на вершины, то в результате получится математический объект или граф с 10 ребрами и 5 вершинами. Нумерацию вершин допустимо выполнять произвольно.
В рассматриваемом примере не используются петли, то есть такие ребра, которые выходят из вершины и сразу же водят в нее. В теории графов существует ряд обозначений:
- G=(V, E), здесь G – граф, V – его вершины, E – ребра;
- |V| – порядок (число вершин);
- |E| – размер графа (число рёбер).
Применительно к рисунку:
|V|=5, |E|=10.
Классификация графов:
- связные, в которых между какой-либо парой вершин расположено от одного и более путей;
- несвязные – хотя бы с одной вершиной, не связанной с другими.
В том случае, когда из любой вершины доступна другая вершина, граф является неориентированным и связным. При невыполнении данного условия для связного графа, его называет ориентированным или орграфом.
Примечание
Степень вершины определяется числом ребер, которые соединяют ее с другими вершинами.
В сумме все степени графа соответствуют удвоенному количеству всех его ребер. К примеру, на рисунке изображен граф со суммой степеней, равной 20:
Орграф отличается от неориентированного графа возможностью перемещаться из вершины h в вершину s без промежуточных вершин лишь тогда, когда ребро выходит из h и входит в s, но не наоборот. Форма записи ориентированного графа:
G=(V, A)
где V – является вершинами, A – определяет направленные ребра.
К третьему типу относят смешанные графы. Такие графы включают направленные и ненаправленные ребра. Формальная запись смешанного графа:
G=(V, E, A)
Источник: kvodo.ru
На рисунке изображен граф с направленными [(e, a), (e, c), (a, b), (c, a), (d, b)] и ненаправленными [(e, d), (e, b), (d, c)…] дугами. Предположим, что имеются два графа:
Данные графы эквиваленты друг другу, так как без изменений в структуре одного графа можно построить второй. Такие графы являются изоморфными, то есть обладают следующим свойством: какая-либо вершина с определенным числом ребер в одном графе имеет тождественную вершину в другом. На приведенном выше рисунке изображена пара изоморфных графов.
В случае, когда каждое ребро графа соответствует некоторому значению в виде веса ребра, граф является взвешенным. При решении задач можно встретить примеры, когда за вес принимают длину, цену маршрута и другие виды измерений. При графическом изображении графа принято указывать весовые значения около ребер.
Путь – последовательность вершин, каждая из которых связана с последующей с помощью ребра.
При совпадении первой и последней вершины путь называют циклом. Длина пути равна количеству составляющих его ребер. К примеру, на рисунке путь является последовательностью [(e), (a), (b), (c)]. Этот путь представляет собой подграф, так как к нему применимо определение последнего, а именно: граф G’=(V’, E’) является подграфом графа G=(V, E), только тогда когда V’ и E’ принадлежат V, E.
Способы представления графа, алгоритмы обхода
Граф, как и другие распространенные типы математических объектов, можно представить на компьютере, то есть сохранить в его памяти. Наиболее известные способы интерпретации графов:
- матрица смежности;
- матрица инцидентности;
- список смежности;
- список ребер.
Первые два метода заключаются в хранении графа в виде двумерного массива или матрицы. Размеры этих массивов определяются числом вершин и/или ребер в определенном графе. Таким образом, размер матрицы смежности – n×n (где n – число вершин), а матрицы инцидентности – n×m (n – число вершин, m – число ребер в графе).
В процессе решения многих задач с применением графов требуется обходить все вершины и ребра, то есть дуги. Обойти граф – значит, пройти все его вершины точно по одному разу. Алгоритмы обхода:
- в глубину;
- в ширину.
Реализация алгоритма обхода заключается в последовательном посещении вершин и исследовании ребер. Не посещенную вершину называют новой. После посещения вершину считают открытой до момента исследования всех инцидентных ей ребер. По итогу манипуляций вершина становится закрытой.
Обход в глубину выполняют, согласно следующим правилам:
- при нахождении в вершине х следует перемещаться в какую-либо другую вершину, не посещенную ранее, с одновременным запоминанием первой дуги;
- в том случае, когда невозможно переместиться в ранее не посещенную вершину из вершины х, требуется вернуться в вершину z, из которой впервые удалось попасть в х, и продолжить обход в глубину из вершины z.
Примечание
Поиск в ширину отличается тем, что за активную принимается такая открытая вершина, которая была посещена последней. В том случае, когда выполняется обход в глубину, чем позднее будет посещена вершина, тем раньше она будет использована.
В качестве примера можно рассмотреть неориентированный граф, изображенный на рисунке:
Обход следует начинать со стартовой вершины 1. Она является активной и единственной, которая открыта. Другие вершины: 2,3,4,5,6 – новые. Вершина 1 обладает тремя инцидентными ребрами – 1–2, 1–4 и 1–6. Можно начать с ребра 1–2. В результате его прохождения открывается вершина 2. Она обладает одним инцидентным ребром 2–1, которое просмотрено. Вершина 2 была просмотрена, в результате чего она преобразуется в закрытую.
Затем по ребру 2–1 можно вернуться в вершину 1. По ребру 1– 4 легко попасть в вершину 4, которая становится открытой. Вершина 4 обладает четырьмя инцидентными ребрами: 4–1, 4–3, 4–5, 4–6. Таким образом, ребро 4–1 просмотрено.
Далее следует рассмотреть ребро 4–3. С его помощью удобно попасть в вершину 3, которая в результате становится открытой. Вершина 3 обладает одним инцидентным ребром 3–4. Данная вершина просмотрена. В результате вершина 3 закрыта, а по ребру 3–4 можно вернуться в вершину 4. Затем следует рассмотреть ребро 4 – 5.
Вершина 5 обладает двумя инцидентными ей ребрами: просмотренным (4–5) и ребром 5–6, по которому можно попасть в вершину 6. Вершина 6 обладает тремя инцидентными ей ребрами: просмотренным 6–5, 6–1 и 6–4. С помощью ребра 6–1 можно попасть в просмотренную вершину 1. По ребру 6–4 просто попасть в просмотренную вершину 4. В результате все вершины графа просмотрены. Порядок посещения вершин: 1, 2, 4, 3, 5, 6.
Основной особенностью и отличием поиска в ширину является выбор в виде активной вершины – такой, которая посещалась раньше, чем остальные. Таким образом, можно сформулировать ключевое свойство обхода в ширину: чем ближе вершина к старту, тем раньше она будет посещена.
Вершина используется путем просмотра одновременно всех вершин, которые ранее не были просмотрены и являются смежными с рассматриваемой вершиной. В результате поиск реализуют по всем вероятным направлением сразу. В первую очередь посещается вершина А, далее смежные с ней вершины, удаленные от А на 1.
Затем посещаются вершины, которые расположены на расстоянии 2 от А, и так далее. Чем ближе вершина к стартовой вершине, тем раньше она будет посещена. Поиск в ширину направлен на определение наиболее короткого из возможных путей.
В качестве примера можно рассмотреть неориентированный граф, изображенный на рисунке:
Обход следует начать со стартовой вершины 1, которая является просмотренной. Вершины 2, 4, 6 и стартовая вершина – смежные. Данные вершины можно отметить, как просмотренные, и поместить в очередь. При рассмотрении вершины 2 можно заметить, что она не обладает смежными вершинами.
Затем нужно рассмотреть вершину 4 с двумя смежными вершинами 3 и 5. Их можно поместить в очередь и отметить, как просмотренные. В результате просмотрены все вершины графа. Порядок посещения вершин: 1, 2, 4, 6, 3, 5.
Как построить граф по матрице смежности
Данная методика отличается удобством, что позволяет представлять плотные графы с количеством ребер (|E|), которое приблизительно соответствует числу вершин в квадрате (|V|2). В процессе требуется заполнить матрицу размером |V| x |V| следующим образом:
A[i][j] = 1 (Если существует ребро из i в j)
A[i][j] = 0 (Иначе)
Метод допустим к применению в случае ориентированных и неориентированных графов. Во втором варианте матрица A имеет вид симметричной, то есть A[i][j] == A[j][i]. Это объясняется тем, что при существовании ребра между i и j, оно является и ребром из i в j, и ребром из j в i. С помощью данного свойства сокращают практически вдвое объем требуемой памяти, в связи с тем, что элементы хранятся лишь в верхней части матрицы, над главной диагональю.
Занятие 3-4: Графы — основные определения¶
Цель: Повторить на практике основные определения теории графов и освоить использование библиотеки визуализации NetworkX¶
Повторить¶
- Определение понятия граф, вершины, ребра, матрица смежности, ориентрованный и не ориентированный граф.
- Гамильтонов цикл.
- Задача коммивояжёра.
- Поиск длины кратчайшего пути при помощи алгоритма Дейкстры.
Основные определения¶
Графом называется конечное множество вершин и множество ребер. Каждому ребру сопоставлены две вершины – концы ребра.
В ориентированном графе одна вершина считается начальной, а другая – конечной.
Если некоторое ребро u соединяет две вершины A и B графа, то говорят, что ребро u инцидентно вершинам A и B, а вершины в свою очередь инцидентны ребру u.
Вершины, соединенные ребром, называются смежными.
Ребра называются кратными, если они соединяют одну и ту же пару вершин (а в случае ориентированного графа – если у них совпадают начала и концы).
Ребро называется петлей, если у него совпадают начало и конец.
Степенью вершины в неориентированном графе называется число инцидентных данной вершине ребер (при этом петля считается два раза, то есть степень — это количество «концов» ребер, входящих в вершину).
Путем на графе называется последовательность ребер, в которой конец одного ребра является началом следующего ребра. Начало первого ребра называется началом пути, конец последнего ребра — концом пути.
Если начало и конец пути совпадают, то такой путь называется циклом.
Путь, который проходит через каждую вершину не более одного раза называется простым путем. Аналогично определяется простой цикл.
Граф называется связным, если между любыми двумя его вершинами есть путь.
Если граф несвязный, то его можно разбить на несколько частей (подграфов), каждая из которых будет связной. Такие части называются компонентами связности.
Деревом называется связный граф не содержащий простых циклов.
Способы представления графов в памяти¶
Матрица смежности¶
При представлении графа матрицей смежности информация о ребрах графа хранится в квадратной матрице (двумерном списке), где элемент A[i][j] равен 1, если ребра i и j соединены ребром и равен 0 в противном случае.
Если граф неориентированный, то матрица смежности всегда симметрична относительно главной диагонали.
Задание 1 Напишите код, заполняющий матрицу смежности для графа, представленного на рисунке ниже
Список смежности¶
При представлении графа списками смежности для каждой вершины i хранится список W[i] смежных с ней вершин.
Например, для графа выше:
W[0] = [1, 2] W[1] = [0, 2] W[2] = [0, 1, 2]
Таким образом, весь граф можно представить одним списком, состоящим из вложенных списков смежности вершин.
W = [[1, 2], [0, 2], [0, 1, 2]]
В таком способе удобно перебирать ребра, выходящие из вершины i (это просто список W[i]), но сложно проверять наличие ребра между вершинами i и j – для этого необходимо проверить, содержится ли число j в списке W[i].
Но в языке Python можно эту часть сделать более эффективной, если заменить списки на множества – тогда проверка существования ребра между двумя вершинами также будет выполняться за О(1).
Задание 2 — В ячейке ниже реализуйте код, который строит список смежности на основе множеств из матрицы смежности, графа из задания 1. Проверьте в коде существование ребер между вершинами графа, изображенного выше. Для каждой пары вершин, между которыми существует ребро, выведите True и False в противном случае.
Взвешенные графы¶
Очень часто рассматриваются графы, в которых каждому ребру приписана некоторая числовая характеристика — вес. Соответствующие графы называются взвешенными.
При представлении графа матрицей смежности вес ребра можно хранить в матрице, то есть A[i][j] в данном случае будет равно весу ребра из i в j. При этом при отсутствии ребра можно хранить специальное значение, например, None.
При представлении графа списками смежности можно поступить двумя способами. Можно в списках смежности хранить пару (кортеж) из двух элементов – номер конечной вершины и вес ребра. Но в этом случае неудобно проверять наличие ребра между двумя вершинами.
Другой способ – хранить списки смежности как ранее, а веса ребер хранить в отдельном ассоциативном массиве (dict в Python), в котором ключом будет пара из двух номеров вершин (номер начальной и конечной вершины), а значением будет вес ребра между этими вершинами.
Гамильтонов цикл¶
Гамильтоновым циклом в графе называют цикл, проходящий через все вершины.
Гамильтонов путь — незамкнутый путь, проходящий через все вершины.
Ниже приведен переборный алгоритм поиска гамильтонова цикла в графе.
Если перенумеровать вершины в графе, то номера вершин в порядке следования их в гамильтоновом цикле образуют некоторую перестановку чисел от 1 до n. Можно перебрать все возможные перестановки и для каждой из них проверить, что данная перестановка соответствует циклу на графе, то есть каждые два соседних элемента в перестановке, а также первый и последний элемент перестановки соединены ребром.
Алгоритм поиска перестановок во многом напоминает алгоритм обхода в глубину, но главное его отличие заключается в том, что если из какой-то вершины не удается продолжить путь дальше (то есть были рассмотрены все ребра и все возможные продолжения привели в тупик), то алгоритм возвращается в предыдущую вершину, при этом покинутая вершина «перекрашивается», то есть с нее снимается отметка о том, что эта вершина была посещена ранее. При этом алгоритм может вернуться в эту вершину еще раз, уже по другому пути (и даже обязан это сделать, если в графе существует гамильтонов путь, так как гамильтонов путь проходит через все вершины).
Пусть n — число вершин в графе, вершины пронумерованы числами от 0 до n-1. Граф задан матрицей смежности A. В глобальной переменной Path будет храниться список вершин, входящих в путь. Функция hamilton() принимает в качестве параметра номер вершины, добавляемой к пути и возвращает значение True, если удалось построить гамильтонов путь и False, если не удалось. Причем если путь построить удалось, то построенный путь будет храниться в списке Path:
Visited = [False] * n Path = [] def hamilton(curr): Path.append(curr) if len(Path) == n: if A[Path[0]][Path[-1]] == 1: return True else: Path.pop() return False Visited[curr] = True for next in range(n): if A[curr][next] == 1 and not Visited[next]: if hamilton(next): return True Visited[curr] = False Path.pop() return False
Функция hamilton() прежде всего добавляет вершину curr в конец списка Path. При этом если длина списка стала равна n, то есть все вершины включены в путь Path, проверяется, что первая и последняя вершина в пути соединены ребром (это не требуется при помощи гамильтонова пути), если это так — то алгоритм возвращает True (цикл найден), в противном случае из списка Path удаляется последний элемент и алгоритм возвращает False (цикл не найден).
Если же длина списка меньше n, то вершина curr отмечается, как посещенная и осуществляется перебор дальнейших продолжений. Последовательно перебираются все оставшиеся вершины next и если вершина next соединена ребром с curr и вершина next не была посещена, то алгоритм рекурсивно запускается из вершины next, пытаясь сделать продолжение пути в вершину next. При этом если рекурсивный вызов из вершины next вернет True, то есть удалось построить цикл, то алгоритм сразу же возвращает True, при этом из списка Path ничего не удаляется, поэтому Path будет хранить полный гамильтонов цикл. Если же ни одно из продолжений не получилось, то осуществляется «откат» вершины curr — она помечается, как непосещенная, удаляется из конца списка Path и управление передается назад, на последнюю вершину в списке Path.
Видно, что сложность алгоритма может быть не менее, чем n!, поэтому для больших графов такой алгоритм непригоден.
Задание 3 — Для графа из задания 3 выведите на экран гамильтонов цикл.
Задача коммивояжера¶
Близкой задачей к задаче нахождения гамильтонова цикла является задача коммивояжера. Коммивояжеру необходимо посетить n городов и вернуться домой. Коммивояжер не хочет посещать города более одного раза и при этом хочет проделать наиболее короткий путь. То есть в неориентированном взвешенном графе необходимо найти путь наименьшей стоимости.
Задача коммивояжера решается аналогично задаче о гамильтоновом пути, но при этом нужно перебрать все возможные пути. При замыкании пути нужно вычислить его вес (лучше это делать не в конце замыкания, а одновременно с добавлением следующей вершины увеличивать вес построенного фрагмента пути на вес рассмотренного ребра) и сравнить вес найденного пути с весом наилучшего известного пути.
Алгоритм Дейкстры¶
Алгоритм Дейкстры назван в честь голландского ученого Эдсгера Дейкстры (Edsger Dijkstra). Алгоритм был предложен в 1959 году для нахождения кратчайших путей от одной вершины до всех остальных в ориентированном взвешенном графе, при условии, что все ребра в графе имеют неотрицательные веса.
Рассмотрим две модели хранения взвешенного графа в памяти. В первой модели (матрица смежности) будем считать, что вес ребра из вершины i в вершину j равен w[i][j], то есть в матрице w хранятся веса ребра для любых двух вершин. Если из вершины i в вершину j нет ребра, то w[i][j]==INF для некоторого специального значения константы INF. Значение INF следует выбирать исходя из задачи.
Алгоритм Дейкстры относится к так называемым «жадным» алгоритмам. Пусть расстояние от начальной вершины start до вершины i хранится в массиве dist[i]. Начальные значения dist[start]=0, dist[i]=INF для всех остальных вершин i. То есть в самом начале алгоритму известен путь из вершины start до вершины start длины 0, а до остальных вершин кратчайшие пути неизвестны. Между тем алгоритм будет постепенно улучшать значения в массиве dist, в результате получит кратчайшие расстояния до всех вершин.
Основная идея для улучшения называется «релаксацией ребра». Пусть из вершины i в вершину j есть ребро веса w[i][j], при этом выполнено неравенство dist[i] + w[i][j] < dist[j]. То есть можно построить маршрут из начальной вершины до вершины i и добавить к нему ребро из i в j, и суммарная стоимость такого маршрута будет меньше, чем известная ранее стоимость маршрута из начальной вершины в вершину j. Тогда можно улучшить значение dist[j], присвоив dist[j] = dist[i] + w[i][j].
В алгоритме Дейкстры вершины красятся в два цвета, будем говорить, что вершина «неокрашенная» или «окрашенная». Изначально все вершины неокрашенные. Если алгоритм Дейкстры покрасил вершину i, то это означает, что найденное значение dist[i] является наилучшим возможным и в последствии не будет улучшаться, то есть значение dist[i] является кратчайшим расстоянием от начальной вершины до вершины i. Если же вершина не покрашена, то величина dist[i] для такой вершины i равна кратчайшему пути из вершины start до вершины i, который проходит только по покрашенным вершинам (за исключением самой вершины i).
На каждом шаге алгоритма Дейкстры красится одна новая вершина. В качестве такой вершины выбирается неокрашенная вершина i с наименьшим значением D[i]. Затем рассматриваются все ребра, исходящие из вершины i, и производится релаксация этих ребер, то есть улучшаются расстояния до вершин, смежных с i.
Алгоритм заканчивается, когда на очередном шаге не останется неокрашенных вершин или если расстояние до всех неокрашенных вершин будет равно INF (то есть эти вершины являются недостижимыми).
Запишем алгоритм Дейкстры. Пусть — число вершин в графе, вершины пронумерованы от 0 до n-1. Номер начальной вершины — start и веса ребер хранятся в матрице w:
INF = 10 ** 10 dist = [INF] * n dist[start] = 0 used = [False] * n min_dist = 0 min_vertex = start while min_dist < INF: i = min_vertex used[i] = True for j in range(n): if dist[i] + w[i][j] < dist[j]: dist[j] = dist[i] + w[i][j] min_dist = INF for j in range(n): if not used[j] and dist[j] < min_dist: min_dist = dist[j] min_vertex = j
Массив used будет хранить информацию о том, была ли покрашена вершина. Сначала инициализируются массивы dist и used. Затем запускается внешний цикл алгоритма, который выбирает неокрашенную вершину с минимальным расстоянием, номер этой вершины хранится в переменной min_vertex, а расстояние до этой вершины — в переменной min_dist. Если же min_dist оказывается равно INF, то значит все неокрашенные вершины являются недостижимыми и алгоритм заканчивает свою работу. Иначе найденная вершина окрашивается и после этого релаксируются все ребра, исходящие из этой вершины.
Для восстановления ответа, то есть для нахождения пути из начальной вершины до всех остальных, необходимо построить дерево кратчайших путей. Это дерево будет состоять из тех ребер, которые были успешно срелаксированы в результате исполнения алгоритма. То есть если происходит релаксация ребра из i в j, то теперь кратчайший маршрут из вершины start до вершины j должен проходить через вершину i и затем содержать ребро i-j. Тем самым вершина i становится предшественником вершины j на кратчайшем пути из начальной вершины до вершины j.
Рассмотрим реализацию алгоритм Дейкстры с восстановлением ответа на графе, хранимым в виде списка смежности на языке Python. Набор вершин, смежных с вершиной i будет храниться в множестве w[i]. Также необходимо хранить веса ребер, будем считать, что для хранения весов ребер используется словарь weight, где ключом является кортеж из двух вершин. То есть вес ребра из i в j хранится в элементе weight[i, j] словаря весов:
dist = [INF] * n dist[start] = 0 prev = [None] * n used = [False] * n min_dist = 0 min_vertex = start while min_dist < INF: i = min_vertex used[i] = True for j in w[i]: if dist[i] + weight[i, j] < dist[j]: dist[j] = dist[i] + weight[i, j] prev[j] = i min_dist = INF for i in range(n): if not used[i] and dist[i] < min_dist: min_dist = dist[i] min_vertex = i
Для нахождения кратчайшего пути из вершины start до вершины j будем переходить от каждой вершины к ее предшественнику:
path = [] while j is not None: path.append(j) j = prev[j] path = path[::-1]
Алгоритм Дейкстры применим только в том случае, когда веса всех ребер неотрицательные. Это гарантирует то, что после окраски расстояние до вершины не может быть улучшено. Если в графе могут быть ребра отрицательного веса, то следует использовать другие алгоритмы.
Задание 4 — Для ненаправленного взвешенного графа, заданного парами вершин и их весов найдите кратчайший путь из вершины 0 в вершину 3 с помощью алгоритма Дейкстры:
- (0, 1, вес = 10)
- (0, 2, вес = 40)
- (1, 2, вес = 15)
- (0, 3, вес = 20)
- (3, 1, вес = 5)
Библиотека NetworkX для визуального представления графов¶
При решении задач контеста удобным инструментом для визуализации графов из примеров является библитотека NetworkX.
Установка библиотеки:
Подключение библиотеки:
NetworkX предназначена для изучения структуры, динамики и функционирования сложных сетей. Она позволяет создавать и хранить графы в стандартных и нестандартных форматах, генерировать много типов случайных и классических графов, анализировать их структуру, строить сетевые модели и создавать новые алгоритмы.
Документация на библиотеку находится по адресу.
Классы графов¶
NetworkX содержит четыре класса графов:
- Graph — граф без кратных рёбер (петли допустимы)
- DiGraph — ориентированный граф без кратных рёбер (петли допустимы)
- MultiGraph — граф с кратными рёбрами (в том числе с кратными
петлями) - MultiDiGraph — ориентированный граф с кратными рёбрами (в том
числе с кратными петлями)
Внутреннее представление графов реализовано в виде списков смежности (словарь словарей словарей). Однако во избежании появления несогласованности, все операции с графами должны производится с использованием API функций библиотеки.
Вершины и рёбра¶
Вершиной может быть любой неизменяемый тип с вычислимой функцией hash().
Например, подойдут соедующие типы Python:
- str
- int
- float
- кортеж из строк и чисел
- frozenset (неизменяемое множество)
Рёбра представляют собой связь двух вершин и чаще вершины имеют привязанные к ним данные — свойства рёбер. Для указания веса ребра, используйте свойство weight.
Создание графа¶
Графы могут быть созданы тремя основными способами:
- явное добавление узлов и рёбер
G = nx.Graph() # создаём экземпляр графа G.add_edge(1, 2) # ребро добавляется сразу со своими вершинами G.add_edge(2, 3) # стандартный вес ребра weight=1 G.add_edge(3, 4, weight = 0.9) # можно задать weight сразу при создании ребра G.add_node(5) # изолированный узел можно добавить отдельно G.add_node(6, x = 1.5, y = -5.0, data = ['any']) # и сразу задать ему любые свойства
- генераторами графов — алгоритмами порождения стандартных сетевых
топологий
G = nx.complete_graph(10) # полносвязный граф с 10 вершинами G = nx.path_graph(10) # 10 узлов, расположенных "в линеечку" G = nx.cycle_graph(10) # 10 узлов, связанных кольцом G = nx.star_graph(5) # звезда с 1 узлом в середине и 5 узлами-лучами G = nx.balanced_tree(2, 3) # сбалансированное двоичное дерево высоты 3 G = nx.empty_graph(10) # граф с 10 вершинами без рёбер
- импорт данных графа из некоторого формата (обычно из файла)
d = {0: {1: {'weight': 10}, 2: {'weight': 20}}, 1: {0: {'weight': 10}, 3: {'weight': 30}}, 2: {0: {'weight': 20}}, 3: {1: {'weight': 30}}} G = nx.Graph(d) dd = nx.to_dict_of_dicts(G) # d == dd
Визуализация графа¶
Визуализация графов — нетривиальная задача! Существует много полноценных библиотек, предназначенных именно для этого: Cytoscape, Gephi, Graphviz или PGF/TikZ для LaTeX. Для их использования можно экспортировать граф из NetworkX в формат GraphML.
Однако, есть и самый простой способ визуализации, встроенный в саму библиотеку NetworkX, при подключении библиотеки
matplotlib.pyplot.
nx.draw(G) # отобразить граф при помощи Matplotlib nx.draw_circular(G) # Использовать расположение circular layout nx.draw_random(G) # Использовать расположение random layout nx.draw_spectral(G) # Использовать расположение spectral layout nx.draw_spring(G) # Использовать расположение spring layout nx.draw_shell(G) # Использовать расположение shell layout nx.draw_graphviz(G) # Использовать graphviz для расположения вершин
Перед выполнением примера ниже не забудьте установить библиотеку matplotlib:
pip install -U matplotlib
Пример визуализации графа №1¶
Выполните приведенный ниже пример в ячейке code
import matplotlib.pyplot as plt import networkx as nx G=nx.path_graph(8) nx.draw(G) plt.savefig("simple_path.png") # сохранить как png файл plt.show() # вывести на экран
Пример визуализации графа №2¶
Пример добавления этикеток на вершины и подкрашивания рёбер:
""" Отрисовка графа через matplotlib, с разными цветами. """ __author__ = """Aric Hagberg (hagberg@lanl.gov)""" import matplotlib.pyplot as plt import networkx as nx G=nx.cubical_graph() pos=nx.spring_layout(G) # позиции всех вершин # вершины nx.draw_networkx_nodes(G, pos, nodelist=[0,1,2,3], # список вершин node_color='r', # красный цвет node_size=500, # размер alpha=0.8) # прозрачность nx.draw_networkx_nodes(G, pos, nodelist=[4,5,6,7], node_color='b', node_size=500, alpha=0.8) # рёбра nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5) # все рёбра nx.draw_networkx_edges(G, pos, edgelist=[(0,1),(1,2),(2,3),(3,0)], width=8, alpha=0.5, edge_color='r') # красные рёбра nx.draw_networkx_edges(G, pos, edgelist=[(4,5),(5,6),(6,7),(7,4)], width=8, alpha=0.5, edge_color='b') # синие рёбра # добавим математические названия вершин labels={} labels[0]=r'$a$' labels[1]=r'$b$' labels[2]=r'$c$' labels[3]=r'$d$' labels[4]=r'$alpha$' labels[5]=r'$beta$' labels[6]=r'$gamma$' labels[7]=r'$delta$' nx.draw_networkx_labels(G, pos, labels, font_size=16) plt.axis('off') plt.savefig("labels_and_colors.png") # сохранить как png картинку plt.show() # вывести на экран
Выполните пример в ячейке ниже.
Пример визуализации графа №3¶
Ещё один пример добавления этикеток на вершины и подкрашивания рёбер:
""" Пример использования Graph как взешенного. """ __author__ = """Aric Hagberg (hagberg@lanl.gov)""" import matplotlib.pyplot as plt import networkx as nx G = nx.Graph() # добавляем рёбра и вершины G.add_edge('a', 'b', weight=0.6) G.add_edge('a', 'c', weight=0.2) G.add_edge('c', 'd', weight=0.1) G.add_edge('c', 'e', weight=0.7) G.add_edge('c', 'f', weight=0.9) G.add_edge('a', 'd', weight=0.3) elarge = [(u,v) for (u,v,d) in G.edges(data=True) if d['weight'] >0.5] # "тяжёлые" esmall = [(u,v) for (u,v,d) in G.edges(data=True) if d['weight'] <=0.5] # "лёгкие" pos = nx.spring_layout(G) # позиции всех вершин # вершины nx.draw_networkx_nodes(G, pos, node_size=700) # рёбра nx.draw_networkx_edges(G, pos, edgelist=elarge, width=6) # "тяжёлые" nx.draw_networkx_edges(G, pos, edgelist=esmall, width=6, alpha=0.5, edge_color='b', style='dashed') # "лёгкие" # метки nx.draw_networkx_labels(G,pos,font_size=20,font_family='sans-serif') plt.axis('off') plt.savefig("weighted_graph.png") # сохранить как png картинку plt.show() # вывести на экран
Матрица
смежности S —
это
квадратная матрица, в которой и число
строк, и число столбцов равно n —
числу вершин графа. В ячейки матрицы
смежности записываются некоторые числа
в зависимости от того, соединены
соответствующие вершины рёбрами или
нет, и от типа графа.
Матрица
смежности для неориентированного графа
Элемент
матрицы смежности sij неориентированного
графа определяется следующим образом:
—
равен единице, если вершины vi и vj смежны;
—
равен нулю, если вершины vi и vj не
смежны.
Если
на диагонали матрицы стоят 1, то это
показывает наличие петель.
|
Пример |
Пример
|
Таким
образом, матрица
смежности неориентированного
графа симметрична относительно главной
диагонали.
Матрица
смежности для ориентированного графа
Элемент
матрицы смежности sij ориентированного
графа определяется следующим образом:
—
равен единице, если из вершины vi в
вершину vj входит
дуга;
—
равен нулю, если из вершины vi в
вершину vj дуга
не входит.
Если
на диагонали матрицы стоят 1, то это
показывает наличие петель.
|
Пример
|
Пример
|
Таким
образом, матрица
смежности ориентированного
графа не симметрична.
9.4. Список ребер
|
Пример
|
9.1-9.4
|
Пример
Матрицы
|
9.5. Матрица достижимости
Матрица
достижимости простого ориентированного
графа G=(V,E) — бинарная матрица замыкания
по транзитивности отношения E (оно
задаётся матрицей смежности графа).
Таким образом, в матрице достижимости
хранится информация о существовании
путей между вершинами орграфа.
Возведение
в степень матрицы смежности орграфа
показывает, за сколько шагов (величина
степени) можно достичь некой вершины.
Способы
построения матрицы достижимости:
-
Перемножение
матриц -
Алгоритм
Уоршелла -
Связанные
понятия
|
Пример Дан
Матрица Матрица Матрица Матрица Если Получим матрицу
Если
|
|||
|
Пример
|
