![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Основные определения теории графов· Число единиц в i-й строке равно степени входа i-ой вершины, i = 1, 2, … , р. · Число единиц с минусом в i-ой строке равно степени выхода i-ой вершины, i = 1, 2, … , р. · Число единиц в матрице равно числу единиц с минусом и равно числу дуг в графе. · В каждом столбце матрицы есть ровно одна единица и ровно одна единица с минусом, так как всякая дуга из одной вершины выходит и в одну вершину входит.
ЛЕКЦИЯ 5.1. Основные определения
Основные определения теории графов
Неформально граф – это диаграмма, состоящая из кружков и линий, соединяющих кружки (рис.1). Кружки называются вершинами графа, а линии – ребрами. Такой граф называется неориентированным. Граф называется ориентированным (рис.2), если каждая линия снабжена стрелкой, показывающей допустимое направление движения от вершины к вершине. Ребро со стрелкой называется дугой. Дадим строгие определения. Определение.Говорят, что задан неориентированный граф Если заданы · Конечное множество · Конечное множество · Антисимметричное бинарное отношение · Тотальная сюръекция Отношение Мощность множества V – число вершин графа – обозначим буквой Проще всего вершины перенумеровать и обозначать каждую вершину её номером. Граф можно нарисовать, если вершины изображать кружками, а ребра – линиями, соединяющими соответствующие пары вершин. На рис. 1 показан простой граф с 4 вершинами и 5 ребрами.
Рис. 2
Говорят, что ребро Вершины, инцидентные одному и тому же ребру, называются смежными. Так же смежными называются ребра, инцидентные одной и той же вершине. Ясно, что бинарное отношение смежности – это симметричное бинарное отношение. Множество вершин графа, смежных данной вершине v, обозначим Если у ребра Дугу Ребро заменяет собой две разнонаправленные дуги. Две стрелки на ребре, как правило, не рисуются. На рис. 2 показан ориентированный граф с множеством вершин На рис. 3 показаны псевдограф и мультиграф. Кратные ребра мультиграфа соединяют одну и ту же пару вершин, концы петли соединяют одну и ту же вершину.
Рис. 3 В дальнейшем, если не будет оговорено противное, мы ограничимся рассмотрением простых графов. Определение. Степенью Множество вершин графа, смежных с данной вершиной Утверждение. (Теорема Эйлера).Сумма степеней всех вершин данного графа равна удвоенному числу ребер графа Доказательство.При подсчете суммы степеней вершин каждое ребро считается дважды, так как каждое ребро простого графа инцидентно ровно двум вершинам. Следствие.Во всяком графе число вершин нечетной степени четно. Доказательство. Если бы это было не так, то сумма степеней вершин графа оказалось бы нечетным числом, что невозможно. Определение. Степенью Определение. Степенью
|