Здавалка
Главная | Обратная связь

Списки смежных вершин

Матрица смежности графа

Пусть G- граф с n вершинами, причем вершинам приписаны номера от 1 до n. Построим квадратную таблицу A размера n x n, в которой элемент, стоящий на пересечении строки с номером I и столбца с номером J, определяется следующим образом:

Она называется матрицей смежности графа. Матрицу смежности можно построить и для ориентированного графа, и для неориентированного, и для графа с петлями. Для обыкновенного графа она обладает двумя особенностями: из-за отсутствия петель на главной диагонали стоят нули, а так как граф неориентированный, то матрица симметрична относительно главной диагонали. Обратно, каждой квадратной матрице порядка , составленной из нулей и единиц и обладающей двумя указанными свойствами, соответствует обыкновенный граф с множеством вершин .

Матрица инцидентности

Другая таблица, ассоциированная с графом - это матрица инцидентности. Для ее построения занумеруем вершины графа числами от 1 до n, а ребра - числами от 1 до m. Матрица инцидентности имеет строк и столбцов, а ее элемент равен 1, если вершина с номером инцидентна ребру с номером , в противном случае он равен нулю.

Рассмотрим граф, представляющий уличную карту Манхэттена в Нью-Йорке. Каждое пересечение двух улиц будет вершиной графа, и соседние перекрестки будут соединяться ребрами. Насколько велик такой график? В основе Манхэттен состоит из 15 авеню, каждое из которых пересекает примерно 200 улиц. Это дает нам примерно 3000 вершин и 6000 ребер, так как каждая вершина соседствует еще с четырьмя вершинами и каждое ребро является общим для двух вершин. Такое небольшое количество данных можно легко и удобно хранить, но у матрицы смежности будет 3000 х 3000 = 9 000 000 ячеек, и почти все они будут пустыми!

Списки смежных вершин

 

Более эффективным способом представления разреженных графов являются связанные списки, в которых хранятся инцидентные соседи каждой вершины. Списки смежности также можно реализовать через матрицы, избегая, таким образом, работы с указателями. Мы можем представить список массивом (или, что эквивалентно, строкой в матрице), введя счетчик к числа элементов и помещая их в первые к элементов массива. Теперь мы можем последовательно обойти элементы от первого к последнему, просто увеличивая счетчик цикла, а не путешествуя по указателям. На первый взгляд кажется, что эта структура данных объединила в себе худшие черты матриц смежности (большой размер) и списков смежности (необходимость поиска ребер). Тем не менее существуют и плюсы. Во-первых, эту структуру данных проще всего запрограммировать, особенно, если речь идет о статичных графах, неизменных после построения. Во-вторых, проблему с размером можно решить, если выделять строки для каждой вершины динамически и делать их соответствующего размера (см vector!).

Таблица ребер.

Еще более простой структурой данных будет массив или связанный список ребер. Работая с ней, сложнее отвечать на такие вопросы, как: "Какие вершины являются соседними для х!" - но она прекрасно подходит для определенных простых процедур, таких, как алгоритм Крускала (Kruskal) остовного дерева минимального веса.

 

Задачи

A. Светофоры

В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.

Первая строка входных данных содержит два числа N и M (0 < N ≤ 100, 0 ≤ MN*(N – 1)/2). В каждой из следующих M строк записаны по два числа i и j (1 <= i,jN), которые означают, что перекрестки i и j соединены тоннелем.

Требуется вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.

Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

Пример

Входные данные Выходные данные
7 10 5 1 3 2 7 1 5 2 7 4 6 5 6 4 7 5 2 1 5 3 3 3 2 2 5 2 3

B. Тропинки

В глухой-глухой тундре есть N чумов, некоторые из которых соединены тропами. Верховный шаман решил провести инвентаризацию тропинок. Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество троп.

В первой строке задается число N (0 ≤ N ≤ 100). В следующих N строках содержится по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i,j) квадратной матрицы стоит единичка, то i-ый и j-ый чумов соединены тропами, а если нолик, то не соединены.

Выведите одно число – количество тропинок

Пример

Входные данные Выходные данные
5 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0

C. Матрица смежности –> список ребер

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

Входные данные включают число n – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрицу смежности.

Выведите список ребер заданного графа (в любом порядке).

Примеры

Входные данные Выходные данные
3 0 1 1 1 0 1 1 1 0 1 2 2 3 1 3

D. Список ребер –> матрица смежности

Простой ориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

На вход программы поступают числа n – количество вершин в графе и m – количество ребер. Затем следует m пар чисел – ребра графа.

Выведите матрицу смежности заданного графа.

Примеры

Входные данные Выходные данные
3 4 1 2 2 3 3 1 3 2 0 1 0 0 0 1 1 1 0

 

E. Степени вершин

Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

Сначала вводится число n – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Выведите n чисел – степени вершин графа.

Примеры

Входные данные Выходные данные
3 0 1 0 1 0 1 0 1 0  

 

F. Стоки и истоки

Вершина ориентированного графа называется истоком, если в нее не входит ни одно ребро и стоком, если из нее не выходит ни одного ребра.

Ориентированный граф задан матрицей смежности. Найдите все вершины графа, которые являются истоками, и все его вершины, которые являются стоками.

Примеры

Входные данные Выходные данные
4 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 3 2 2 4

 

G. Регулярный граф

Неориентированный граф называется регулярным, если все его вершины имеют одинаковую степень. Для заданного списком ребер графа проверьте, является ли он регулярным.

Примеры

Входные данные Выходные данные
3 3 1 2 1 3 2 3 YES
3 2 1 2 2 3 NO

H. Турнир

Ориентированный граф называется турниром, если между любой парой его различных вершин существует ровно одно ребро. Для заданного списком ребер графа проверьте, является ли он турниром.

Примеры

Входные данные Выходные данные
3 3 1 2 1 3 3 2 YES
3 4 1 2 2 1 2 3 1 3 NO




©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.