АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Смежность и инцидентность

Читайте также:
  1. В XVIII в. психология развивалась под влиянием возникновения новых мировоззренческих представлений.
  2. Выступление на конференции по итогам сплошной педпрактики студентов в АПК. 3 страница
  3. Гармония золотых пропорций 4 страница
  4. Глава I. ПРЕДМЕТ ЛОГОПЕДИИ
  5. Избранные главы оптики и квантовой физики. Квантовая физика 3 страница
  6. Изоморфизм графов
  7. К. Халл (1884-1952)
  8. Матрица инциденций
  9. Научение: изменение когнитивной структуры, ценностей и валентностей
  10. Основные принципы эпидемиологии психосоматических расстройств
  11. Память и восприятие
  12. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Пусть v1, v2 - вершины, е = (v1, v2) - соединяющее их ребро. Тогда вершина v1 и ребро е инцидентны, вершина v2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Степенью вершины v графа G(V,E) называется число ребер, инцидентных данной вершине. Обозначение: .

Вершина, имеющая степень 0 называется изолированной, имеющая степень 1 – висячей.

Пример. Для графа, изображенного на рис. 3.5: вершина 3 – изолированная, вершины 1 и 4 - висячие.

Пример. Для графа, изображенного на рис. 3.3.

Ребро e1 инцидентно вершинам v1 и v2. Вершина v1 инцидентна ребрам e1 и e2. Ребра e1 и e2 – смежны. Вершины v1 и v2 – смежны.

. p(G)=3, q(G)=5.

Т.о. можно заметить, что .

Теорема Эйлера: .

Доказательство данной теоремы вытекает из того, что каждое ребро дает двойной вклад в сумму степеней вершин.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)