Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин. Вершиной графа могут быть города, а ребрами дорога между городами. Или, например, вершинами могут быть аккаунты в VK. А ребра между ними означает, что два аккаунта находятся в друзьях друг у друга.
Графы бывают разные. На этом семинаре нам важно, что они бывают:
i в вершину j.i в вершину j, и наоборот.Способы задания графа:
Нам понадобится только матрица смежности. Важно помнить, что для неориентированных графов она симметрична.
Давайте вспомним как пользоваться матрицами в R.
Для этого нам понадобится функция ‘matrix’. У неё есть 3 главных аргумента:
data - то чем заполняем матрицу, это может быть число или массив.nrow - количество строк в матрице.ncol - количество столбцов в матрице.Давайте попробуем создать матрицу, состоящую из 0 размером 3 на 4.
matrix(data = 0, nrow = 3, ncol = 4)## [,1] [,2] [,3] [,4]
## [1,] 0 0 0 0
## [2,] 0 0 0 0
## [3,] 0 0 0 0А теперь давайте попробуем заполнить матрицу с помощью массива.
matrix(data = 1:12, nrow = 3, ncol = 4)## [,1] [,2] [,3] [,4]
## [1,] 1 4 7 10
## [2,] 2 5 8 11
## [3,] 3 6 9 12Как видим массив заполнялся по столбцам, сначала первый, потом второй и так далее. Если вы хотите заполнить его построчно, то вы можете воспользоваться еще одним параметром byrow. Давайте попробуем.
matrix(data = 1:12, nrow = 3, ncol = 4, byrow = TRUE)## [,1] [,2] [,3] [,4]
## [1,] 1 2 3 4
## [2,] 5 6 7 8
## [3,] 9 10 11 12Матрица – это двумерный массив, поэтому обращаться к ней можно так же, но при этом нужно указывать уже 2 индекса(строка и столбец). Давайте зададим случайную матрицу 4 на 5 и найдем ее значение, которое находится в 3 строчке, 4 столбце.
(M <- matrix(sample(-100:100, 20), nrow = 4, ncol = 5))## [,1] [,2] [,3] [,4] [,5]
## [1,] 6 -80 26 90 -100
## [2,] 78 62 -43 69 44
## [3,] 1 -62 -18 89 56
## [4,] -4 -79 9 49 -40M[3,4]## [1] 89Также указав один индекс мы можем получить целую строчку или целый столбец.
M[3,]## [1] 1 -62 -18 89 56M[,4]## [1] 90 69 89 49Если мы хотим присвоить какое-то значение, то мы указываем какой элемент матрицы хотим поменять.Ставим знак присвоения и пишем новое значение. Давайте поменяем значение в 3 строчке,4 столбце матрицы M.
M[3,4] <- 25
print(M)## [,1] [,2] [,3] [,4] [,5]
## [1,] 6 -80 26 90 -100
## [2,] 78 62 -43 69 44
## [3,] 1 -62 -18 25 56
## [4,] -4 -79 9 49 -40При реализации алгоритмов нам нужно будет каждый раз создавать граф, добавлять и удалять ребра. Поэтому напишем готовые функции для этого.
Чтобы создать граф достаточно создать матрицу из нулей размера n на n.
newGraph <- function(n){
G <- matrix(data = 0, nrow = n, ncol = n)
return(G)
}Давайте попробуем использовать функцию. Создадим граф из 6 вершин.
R <- newGraph(6)
print(R)## [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] 0 0 0 0 0 0
## [2,] 0 0 0 0 0 0
## [3,] 0 0 0 0 0 0
## [4,] 0 0 0 0 0 0
## [5,] 0 0 0 0 0 0
## [6,] 0 0 0 0 0 0Пустой граф нам не очень интересен, поэтому нужно заполнить его ребрами. Представим, что мы работаем с неориентированным графом и нам не важен вес. Чтобы добавить ребро, нужно знать в какой граф мы хотим это сделать, а также вершины между которыми будет ребро. На выходе у нас будет обновленная матрица.
addEdge <- function(G, i, j){
G[i, j] <- 1
G[j, i] <- 1
return(G)
}Добавим несколько ребер в наш граф R.
R <- addEdge(R, 1, 2)
R <- addEdge(R, 2, 5)У ребер бывает вес, поэтому при добавлении ребра хотелось бы иметь параметр w, который отвечает за вес. Улучшим нашу функцию.
addEdge <- function(G, i, j, w = 1){
G[i, j] <- w
G[j, i] <- w
return(G)
}Если мы не хотим добавлять вес, то он будет по дефолту равен 1. Добавим еще ребер в граф R.
R <- addEdge(R, 1, 2, 10)
R <- addEdge(R, 2, 5)Граф бывает ориентированный. В этом случае мы должны поменять только 1 значение, а не 2. Введем еще один бинарный параметр directed для обозначения типа графа. С помощью if можно удостовериться в типе графа и изменить либо 1, либо 2 значения.
addEdge <- function(G, i, j, w = 1, directed = FALSE){
if(directed == FALSE){
G[i, j] <- w
G[j, i] <- w
}else{
G[i, j] <- w
}
return(G)
}Давайте добавим в граф R ориентированое ребро из вершины 5 в вершину 6 с весом 19.
R <- addEdge(R, 5, 6, 19, directed = TRUE)
print(R)## [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] 0 10 0 0 0 0
## [2,] 10 0 0 0 1 0
## [3,] 0 0 0 0 0 0
## [4,] 0 0 0 0 0 0
## [5,] 0 1 0 0 0 19
## [6,] 0 0 0 0 0 0Наша функция почти идеальна, оптимизируем ее немного. Во - первых, вне зависимости от типа графа мы выполним операцию G[i, j] <- w. Поэтому вынесем ее за if. Когда if небольшой можно использовать функцию ifelse.
addEdge <- function(G, i, j, w = 1, directed = FALSE){
G[i, j] <- w
ifelse(directed == FALSE, G[j, i] <- w)
return(G)
}Удаление ребра эквивалентно добавлению ребра с весом 0. Поэтому можно взять код оттуда и удалить переменную w
removeEdge <- function(G, i, j, directed = FALSE){
if(directed == FALSE){
G[i, j] <- 0
G[j, i] <- 0
}else{
G[i, j] <- 0
}
return(G)
}Удалим в графе R недавно созданное ребро из вершины 5 в вершину 6.
R <- removeEdge(R, 5, 6)
print(R)## [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] 0 10 0 0 0 0
## [2,] 10 0 0 0 1 0
## [3,] 0 0 0 0 0 0
## [4,] 0 0 0 0 0 0
## [5,] 0 1 0 0 0 0
## [6,] 0 0 0 0 0 0