Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Способы задания графов

1. Матрица смежности вершин графа – квадратная матрица n-ного порядка, где n – число вершин. Строки и столбцы матрицы соответствуют вершинам графа. Элементы р_ij равны числу дуг, направленных из i в j. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1. В случае неориентированного графа ему вместе с ребром (X_i X_j) принадлежит ребро (X_j X_i).

2. Матрица смежности дуг – квадратная матрица m-ного порядка, m – число дуг. Строки и столбцы матрицы соответствуют дугам графа. Элементы q_ij равны 1, если дуга у_i непосредственно предшествует дуге y_j, и 0 в остальных случаях.

3. Матрица смежности ребер неориентированного графа – матрица m-ного порядка, m – число ребер с элементами q_ij = 1, если ребра y_i y_j имеют общую вершину, и 0 в остальных случаях.

4. Матрица инцидентности орграфа – прямоугольная матрица, размерности n^хm, строки которой соответствуют вершинам, а столбцы дугам орграфа. Элементы r_ij равны 1, если дуга y_j исходит из i-той вершины и равны 0, если дуга не инцидентна i-той вершине.

В случае неориентированного графа будет или 0, или 1.

Алгоритм Прима, Краскала (назначение, пошаговая реализация)

Пусть G неориентированный связный граф. Любой связный подграф G* из множества (G* с G) содержащий все вершины графа и не имеющий циклов называется остовом G или остовным деревом.

Постановка задачи:

Имеется связный граф, каждому ребру которого поставлено в соответствие неотрицательное число, называемое весом ребра. Требуется найти остовное дерево минимального веса. Вес дерева равен сумме весов ребер, входящих в него.

Алгоритм Прима

1. Выбирается подграф G₁ из множества G, вершинами которого являются вершины графа, имеющего одно ребро, выбранное из ребер графа G имеющих минимальный вес. На каждом последующем шаге уже построенному графу добавляется одно ребро.

…

К. Если подграф G_к-1 из множества G уже построен, то граф G_к получается из G_к-1 добавлением ребра L обладающего свойствами:

1. L инцидентно какому-либо ребру G_к-1

2. При добавлении к L G_к-1 не образуется циклов.

3. L имеет минимальный вес среди ребер, удовлетворяющих условию 1 и 2.

Алгоритм Крускала

1. Выбирается подграф G₁ из множества G, вершинами которого являются вершины графа, имеющего одно ребро, выбранное из ребер графа G имеющих минимальный вес. На каждом последующем шаге уже построенному графу добавляется одно ребро.

К. Если подграф G_к-1 из множества G уже построен, то граф G_к получается из G_к-1 добавлением ребра L обладающего cвойствами:

1. При добавлении L G_к-1 не образуется циклов

2. L имеет минимальный вес среди ребер, удовлетворяющих условию 1.