Особенности данного представления[]
Используется для любых графов, даже если есть петля.
В каждом столбце обязательно должны стоять две единицы (либо 1 и -1 в случае ориентированного графа).
2)
Список рёбер
Список, где каждому ребру графа соответствует строка, в которой хранятся две вершины, инцидентные ребру.
Р
азмер
занимаемой памяти:
Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными.
43. Эйлеровы графы (1). Гамильтоновы цепи и циклы (2). Гамильтоновы графы (3).
1)
2 и 3)
44. Ациклический граф. Лес. Деревья. Свойства деревьев (1). Корневые деревья. Высота ордерева. (2)
1)
2)
45. Остовное дерево графа (1). Минимальные остовы графов (2).
1)
2)
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
46. Полный двудольный граф.
Полный
двудольный граф 
—
это двудольный граф, такой что для любых
двух вершин 
и 
, 
является
ребром в 
.
Полный двудольный граф с долями
размера 
и 
обозначается
как 
.
Графы
называются звёздами,
все полные двудольные графы,
являющиеся деревьями,
являются звёздами.Граф
называется клешнёй и
используется для определения графов
без клешней.Граф
иногда
называется «коммунальным графом»,
название восходит к классической задаче
«домики
и колодцы»,
в современной интерпретации использующей
«коммунальную» формулировку (подключить
три домика к водо- электро- и газоснабжению
без пересечений линий на плоскости);
задача неразрешима ввиду непланарности графа
.
47. Планарные (плоские) графы. Формула Эйлера.
Планарный граф — граф, который может быть изображён на плоскости без пересечения ребер. Иначе говоря, граф планарен, если он изоморфен некоторому плоскому графу, то есть графу, изображённому на плоскости так, что его вершины — этоточки плоскости, а рёбра — непересекающиеся кривые на ней. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, так называемая внешняя грань.
Формула Эйлера
Для
связного плоского графа справедливо
следующее соотношение между количеством
вершин 
,
ребер 
и
граней 
(включая
внешнюю грань):
Оно было найдено Эйлером в 1736 г.[1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум, а, например, для тора — нулю.
Формула имеет множество полезных следствий. Во-первых, все плоские укладки одного графа имеют одинаковое количество граней. Во-вторых, если каждая грань ограничена не менее чем тремя рёбрами (при условии, что в графе больше двух ребер), а каждое ребро разделяет две грани, то
следовательно,
то есть, при большем числе рёбер такой граф заведомо непланарен. Обратное утверждение не верно: в качестве контрпримера можно взять граф Петерсена. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.
Общая формула также легко обобщается на случай несвязного графа:
где 
—
количество компонент связности в графе.