|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Формула ЭйлераТеорема (Понтрягин-Куратовский) Граф планарен тогда и только тогда, когда он не содержит в качестве частей графы К5 и К3,3 (быть может с добавочными вершинами степени 2).
(ВИКИПЕДИЯ – простейшие свойства) Формула Эйлера Для связного плоского графа справедливо следующее соотношение между количеством вершин , ребер и граней (включая внешнюю грань): Формула имеет множество полезных следствий. Во-первых, все плоские укладки одного графа имеют одинаковое количество граней. Во-вторых, если каждая грань ограничена не менее чем тремя рёбрами (при условии, что в графе больше двух ребер), а каждое ребро разделяет две грани, то следовательно, то есть, при большем числе рёбер такой граф заведомо непланарен. Обратное утверждение не верно: в качестве контрпримера можно взять граф Петерсена. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5. Общая формула также легко обобщается на случай несвязного графа: где — количество компонент связности в графе.
12. Степени вершин графа, теорема о сумме степеней и следствие из неё. (википедия) Степень вершины (валентность) — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды. Степень вершины обозначается как (в западных источниках — ). Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.) |