9.2 Grafik dan Jaringan Pada bagian ini akan dibahas tentang dasar-dasar graf dan jaringan diantaranya definisi mereka. Kemudian kita akan membahas beberapa sifat dari teori graf.

Grafis dan jaringan di ketahui V = {1,2,…,15} dan grafis G tak terarahkan akan kita tampilkan pada sebuah visualisasi dengan 23 batas yang tak terarahkan.

library(igraph)
## Warning: package 'igraph' was built under R version 4.2.3
## 
## Attaching package: 'igraph'
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## The following object is masked from 'package:base':
## 
##     union
G <- sample_gnp(20, 0.35)
plot(G)

Data V = {1,2,..,15} akan kita visualisasikan sebagai berikut

library(igraph)
N <- barabasi.game(20)
plot(N)

undirected graphics

Grafik acak tidak terarah dihasilkan di bawah model Erd¨os–R´enyi dengan 15 simpul dan probabilitas menghubungkan dua simpul sama dengan 0,5.

as_adjacency_matrix(G)
## 20 x 20 sparse Matrix of class "dgCMatrix"
##                                              
##  [1,] . . . 1 . . . . . . . . . 1 1 . . 1 . 1
##  [2,] . . 1 1 1 . . 1 1 . . . 1 . . . . . . .
##  [3,] . 1 . 1 1 . . . . . 1 1 1 1 . 1 1 1 1 .
##  [4,] 1 1 1 . 1 1 . . . 1 . . . . 1 . . . . .
##  [5,] . 1 1 1 . . . 1 1 1 . 1 1 . . . . . . .
##  [6,] . . . 1 . . . . . . . . . 1 1 1 . . . .
##  [7,] . . . . . . . . . . . . . . 1 . . . . .
##  [8,] . 1 . . 1 . . . 1 . 1 . . . . . . 1 . 1
##  [9,] . 1 . . 1 . . 1 . . 1 . . 1 1 . 1 . . .
## [10,] . . . 1 1 . . . . . 1 . 1 . . . 1 . . .
## [11,] . . 1 . . . . 1 1 1 . 1 . 1 . 1 . . . .
## [12,] . . 1 . 1 . . . . . 1 . 1 1 1 . 1 1 1 .
## [13,] . 1 1 . 1 . . . . 1 . 1 . . . . . 1 . 1
## [14,] 1 . 1 . . 1 . . 1 . 1 1 . . 1 . . . . .
## [15,] 1 . . 1 . 1 1 . 1 . . 1 . 1 . . 1 1 . 1
## [16,] . . 1 . . 1 . . . . 1 . . . . . 1 . . 1
## [17,] . . 1 . . . . . 1 1 . 1 . . 1 1 . . . .
## [18,] 1 . 1 . . . . 1 . . . 1 1 . 1 . . . 1 .
## [19,] . . 1 . . . . . . . . 1 . . . . . 1 . .
## [20,] 1 . . . . . . 1 . . . . 1 . 1 1 . . . .

komputasikan matriks kedekatan dari jaringan melalui fungsi as adjacency matrix() dari package igraph.

as_adjacency_matrix(N)
## 20 x 20 sparse Matrix of class "dgCMatrix"
##                                              
##  [1,] . . . . . . . . . . . . . . . . . . . .
##  [2,] 1 . . . . . . . . . . . . . . . . . . .
##  [3,] 1 . . . . . . . . . . . . . . . . . . .
##  [4,] 1 . . . . . . . . . . . . . . . . . . .
##  [5,] 1 . . . . . . . . . . . . . . . . . . .
##  [6,] 1 . . . . . . . . . . . . . . . . . . .
##  [7,] 1 . . . . . . . . . . . . . . . . . . .
##  [8,] . 1 . . . . . . . . . . . . . . . . . .
##  [9,] 1 . . . . . . . . . . . . . . . . . . .
## [10,] 1 . . . . . . . . . . . . . . . . . . .
## [11,] 1 . . . . . . . . . . . . . . . . . . .
## [12,] 1 . . . . . . . . . . . . . . . . . . .
## [13,] . . . . . . 1 . . . . . . . . . . . . .
## [14,] 1 . . . . . . . . . . . . . . . . . . .
## [15,] . . . . . . . . . . . . 1 . . . . . . .
## [16,] . . . . . . . . . 1 . . . . . . . . . .
## [17,] . . . . . . 1 . . . . . . . . . . . . .
## [18,] . 1 . . . . . . . . . . . . . . . . . .
## [19,] 1 . . . . . . . . . . . . . . . . . . .
## [20,] 1 . . . . . . . . . . . . . . . . . . .

9.2.3 Properti Matriks Laplacian

Matriks Laplacian memberi tahu kita banyak tentang sifat-sifat tentang grafik. Untuk menunjukkan properti ini kita harus menggunakan alat dari aljabar linier. Di bagian ini kita akan membahas beberapa sifat terkenal dari matriks Laplacian. Di sini kami menganggap kami memiliki grafik yang tidak diarahkan. Jika kita memiliki grafik berarah, yaitu, sebuah jaringan, kami membuat tepi yang diarahkan sebagai tepi yang tidak diarahkan.

Misalkan kita memiliki matriks Laplacian L dengan…

library(pracma)
## Warning: package 'pracma' was built under R version 4.2.3
L <- matrix(c(3, -1, -1, -1, 0, -1, 3, -1, 0, -1, -1, -1, 3, -1, 0, -1,
0, -1, 2, 0, 0, -1, 0, 0, 1), 5, 5)
nullspace(L)
##           [,1]
## [1,] 0.4472136
## [2,] 0.4472136
## [3,] 0.4472136
## [4,] 0.4472136
## [5,] 0.4472136
LL <- L
LL[1,] <- LL[1,]/LL[1,1]
LL[2,] <- LL[2,]/LL[2,2]
LL[3,] <- LL[3,]/LL[3,3]
LL[4,] <- LL[4,]/LL[4,4]
LL[5,] <- LL[5,]/LL[5,5]

komputasikan dengan fungsi eigen().

E <- eigen(LL)

gunakan $values. unutk mendapat nilai eigen

E$values
## [1] 1.767592e+00 1.333333e+00 1.333333e+00 5.657415e-01 1.340063e-16

jumlahkan semuanya dengan fungsi sum().

sum(E$values)
## [1] 5