Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Степени вершины
Если в графе пара вершин такова, что , то вершины называются смежными; в этой ситуации каждая из них называется инцидентной ребру , а ребро называется инцидентным каждой из вершин . Если вершина и ребро инцидентны, то пишут . Количество ребер, инцидентных данной вершине , называется ее степенью или локальной степенью графа в вершине иобозначают через . Для неориентированного графа . Вершина с нулевой степенью называется изолированной. Вершина, степень которой равна единице, называется висячей. Если ребро (дуга) инцидентно только одной вершине, то его называют петлей. Ребра называют кратными, если они инцидентны одним и тем же вершинам. Исторически первой теоремой теории графов является утверждение, принадлежащее Эйлеру и связывающее количество ребер, вершин и их степеней. Теорема 2. Сумма степеней вершин -графа равна удвоенному числу его ребер: . Доказательство. Поскольку любое ребро инцидентно двум вершинам, то в сумме степеней всех вершин графа каждое ребро учитывается дважды. Следствие. В любом графе число вершин нечетной степени четно. Доказательство. Пусть и – множества вершин четной и нечетной степени соответственно. Очевидно, что . Первое слагаемое четно (как сумма четных чисел). Значит второе слагаемое также должно быть четным, а это при суммировании нечетных чисел возможно, если только их количество четно. Для орграфов вместо степени вершины вводят понятие полустепеней: полустепень исхода – это число дуг, выходящих из вершины ; полустепень захода – это число дуг, входящих в вершину . Очевидно, что .
|