Приложение 6.А. ЭЛЕМЕНТАРНЫЕ СВЕДЕНИЯ О ГРАФАХ
Теория графов имеет продолжительную историю, обширную литературу и многочисленные приложения Очевидно, знакомство с некоторыми элементарньми понятиями теории графов может очень существенно способствовать пониманию большинства тех алгоритмов обработки изображений, в которых используется аппарат теории графов. Целью данного приложения является изложение некоторых наиболее общих понятий теории графов
Граф представляет собой множество точек, или вершин, связанных между собой линиями, или ребрами. Примеры графов приведены на рис. 6.10, 6.11, б - 6.13.
Степень вершины графа равна числу ребер, инцидентных этой вершине. Так, все вершины графа, приведенного на рис. 6.12, имеют четвертую степень, а граф, приведенный на рис. 6.13, имеет вершины различных степеней — второй и третьей. Улицы города являются примером графа — его вершины соответствуют перекресткам и тупикам, а ребра представляют части улиц, связывающие перекрестки или ведущие в тупики. В подобном «графе улиц» большая часть вершин имеет четвертую степень, а тупиковые улицы заканчиваются вершинами первой степени.
Ориентированным называется граф, некоторым или всем ребрам которого приписана определенная ориентация. В нашем примере с улицами города граф превращается в ориентированный, если учитываются только улицы с односторонним движением. В таких графах различают степень исхода и степень захода вершины, которые определяются как число дуг, исходящих из вершины и входящих в нее соответственно. Модификации этих терминов были предложены нами в разд. 6 7.
Маршрутом, связывающим вершину А с вершиной В, называется последовательность ребер, которую необходимо пройти, продвигаясь от вершины 
вершине В. Маршрут, начальная и конечная вершины которого совпадают, называется контуром. Граф называется связным, если для любой пары его вершин существует маршрут.
Деревом называется связный граф, не содержащий контуров.
Граф, содержащий некоторые или все вершины и некоторые или все ребра графа 
и не содержащий никаких иных вершин и ребер, называется подграфом указанного графа 
Подграф связного графа 
содержащий все вершины графа 
и те его ребра, которые необходимы для того, чтобы данный подграф являлся связным и не содержал контуров, называется остовным деревом графа 
Общепринятый способ изображения деревьев заключается в выборе вершины в качестве корня дерева, последующем размещении под ней всех соединенных с первоначально выделенной вершин и т. д. (см. рис 6.3). Все вершины, связанные с расположенной над ними вершиной А, называются ее дочерними вершинами (непосредственными потомками), а вершина А называется их вершиной-предком (родительской вершиной) 1.
