Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Бурков В.Н. Элементы теории графов
 
djvu / html
 

i= \,n; эйлеров граф является объединением контуров, попарно
не имеющих общих ребер.
Определим матрицу смежности графа как квадратную мат-
рицу п х п, элемент ау которой равен единице, если (i,j) Е V, и
нулю, если (г, у) "е" V, i,j E X. Для неориентированного графа
матрица смежности всегда симметрическая.
Определим матрицу инциденций для ребер графа как прямо-
угольную матрицу п х т, элемент г у которой равен единице, если
вершина z инцидентна ребруу, и нулю в противном случае, г = \, п ,
j= \,m . Аналогично определяется матрица инциденций для дуг
графа - как прямоугольная матрицу т х п, элемент гу которой
равен плюс единице, если дуга СУ/ исходит из вершины z, минус
единице, если дута СУ, заходит в вершину г, и нулю в остальных
случаях, г = \,n,j= \,т
Деревом называется связный граф без простых циклов, имею-
щий не менее двух вершин. Для дерева т = п - 1, а число висячих
вершин равно и/ = 2 + /^(z — 2) nf . Легко показать, что в дереве
г>2
любые две вершины связаны единственной цепью.
Прадеревом называется ориентированное дерево, у которого
одна из вершин, называемая корнем, не имеет заходящих дуг, а
степени захода остальных вершин равны единице.
Плоским (планарным) называется граф, который можно изо-
бразить на плоскости так, что различным вершинам соответствуют
различные кружки и никакие два ребра не имеют общих точек,
отличных от их границ (не пересекаются). Для плоского графа
существует понятие грани - части плоскости, ограниченной ребра-
ми и не содержащей внутри себя ни вершин, ни ребер. Для просто-
ты определения грани в дальнейшем в основном будем рассматри-
вать графы без висячих вершин. Например, дерево имеет всего
одну внешнюю грань - всю плоскость. Степенью грани называется
число ее граничных ребер (висячие ребра считаются дважды).
Обозначим р - число граней плоского графа, pk - число его граней,
имеющих степень k, qt - степень z'-ой грани. Можно показать, что
имеет место j i=\ k: pt>0

 

1 2 3 4 5 6 7 8 9 10 20


Математика