Основы теории графов и представление
1. Понятие и введение
Теория графов — это раздел дискретной математики, дисциплина, изучающая графы.
Граф — это математическая структура, используемая для моделирования попарных отношений между объектами, состоящая из «узлов» или «вершин» (Vertex) и «рёбер» (Edge), соединяющих эти вершины.
Стоит отметить, что множество вершин графа не может быть пустым, но множество рёбер может быть пустым. Граф может быть неориентированным, то есть рёбра в графе не различают направление при соединении вершин. В противном случае граф называется ориентированным. На рисунке ниже слева показана типичная структура неориентированного графа, а на рисунке ниже справа — ориентированный граф. Все графы, рассматриваемые в этой главе, являются неориентированными.
Классификация графов: невзвешенные графы и взвешенные графы. Обладают ли рёбра, соединяющие узлы, связанными с ними числовыми значениями; если да, то это взвешенный граф; иначе — невзвешенный граф.
Связность графа:В теории графов понятие связного графа основано на понятии связности. В неориентированном графе G, если существует путь, соединяющий вершину i с вершиной j (конечно, также должен существовать путь из j в i), то говорят, что i и j соединены. Если G — ориентированный граф, то все рёбра на пути, соединяющем i и j, должны иметь одинаковое направление. Если любые две вершины графа соединены, граф называется связным. Если граф ориентированный, он называется сильно связным графом (примечание: пути должны существовать в обоих направлениях). Связность графа — фундаментальное свойство графов.
Полный граф:Полный граф — это простой неориентированный граф, в котором каждую пару различных вершин соединяет ровно одно ребро.
Петля:Начальная и конечная точки ребра являются одной и той же вершиной.
Параллельное ребро:Между двумя вершинами существует несколько рёбер.
II. Примечания по применимости
Графы могут использоваться для моделирования многих типов отношений и процессов в физических, биологических, социальных и информационных системах, и многие практические задачи могут быть представлены графами. Поэтому теория графов стала мощным математическим инструментом для многих дисциплин, таких как исследование операций, кибернетика, теория информации, теория сетей, теория игр, физика, химия, биология, общественные науки, лингвистика и информатика. Когда подчёркивается её применение к реальным системам, сеть иногда определяется как граф, в котором отношения между атрибутами (такими как имена) представлены в виде узлов и/или рёбер.
3. Формы представления графов
Матрица смежности:1 означает наличие связи, 0 означает отсутствие связи.
Список смежности:Представляет только информацию о вершинах, смежных с данной вершиной
Список смежности подходит для представления разреженных графов.
Матрица смежности подходит для представления плотных графов.
Пример кода на Java
Загрузка пакета исходного кода:Скачать
(1) Матрица смежности
Код файла src/example/graph/DenseGraph.java:
/**
* Матрица смежности
*/
public class DenseGraph {
// Количество узлов
private int n;
// Количество рёбер
private int m;
// Является ли граф ориентированным
private boolean directed;
// Конкретные данные графа
private boolean[][] g;
// конструктор
public DenseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g инициализируется как boolean-матрица n*n, каждый g[i][j] равен false, что означает отсутствие рёбер
// false — значение по умолчанию для переменных типа boolean
g = new boolean[n][n];
}
// Возвращает количество узлов
public int V(){ return n;}
// Возвращает количество рёбер
public int E(){ return m;}
// Добавить ребро в граф
public void addEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
if( hasEdge( v , w ) )
return;
g[v][w] = истина;
if( !directed )
g[w][v] = истина;
m ++;
}
// Проверить, существует ли ребро из v в w в графе
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w];
}
}
(2) Список смежности
код файла src/example/graph/SparseGraph.java:
import java.util.Vector;
/**
* Список смежности
*/
public class SparseGraph {
// Количество узлов
private int n;
// Количество рёбер
private int m;
// Является ли граф ориентированным
private boolean directed;
// Конкретные данные графа
private Vector<Integer>[] g;
// конструктор
public SparseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g инициализируется как n пустых векторов, то есть каждый g[i] пуст, т. е. рёбер нет
g = (Vector<Integer>[])new Вектор[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Integer>();
}
// Возвращает количество узлов
public int V(){ return n;}
// Возвращает количество рёбер
public int E(){ return m;}
// Добавить ребро в граф
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
g[v].добавьте(w);
if( v != w && !directed )
g[w].добавьте(v);
m ++;
}
// Проверить, существует ли ребро из v в w в графе
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v].elementAt(i) == w )
return true;
return false;
}
}