Списочное представление графов

 

Более экономным в смысле расхода памяти является представление графа с помощью списка пар вершин, соответствующим его ребром. В случае орграфа необходимо либо помещать вершины-отправители и узлы получатели, либо (для смешанного графа) иметь три строки, где третья строка указывает, какая ветвь неориентирована.

Во многих случаях лучшим способом описания графов является структура данных, называемая списком смежности. Эта структура для каждой вершины, помеченной признаком «начало», содержит список вершин, смежных с данной вершиной. Каждый список вершин заканчивается признаком «конец». Размерность такой структуры равна m+n для орграфа и n+2m – для неориентированного графа. Описание графа в виде списка инцидентности благодаря признакам «нач» и «кон» может выполняться не в виде таблицы, а виде строки, что позволяет экономить память.

Задачи

2.1. Для графов предыдущего пункта записать их списочное представление.

2.2. Построить графы по их списочному представлению:

 

нач 1 – 1 кон

нач2 – 1 – 2 кон

а)нач 3 – 1 – 2 – 4 – 5 – 3 кон

нач 4 – 1 – 4 – 5 кон

нач 5 – 1 – 5 кон;

 

 

б)

 

 

Заключение

 

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

 

Литература

1. Ерусалимский Я.М. Дискретная математика. - М.: Вузовская книга, 1998, С.267-271.

2. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1977, С. 101-110.

3. Акимов О. Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001 – 352с.: ИЛ.

 

 

 

Методическая разработка составлена

доцентом кафедры АСУ Т.Авакян