Образовательный блог – всё для учебы

Определение: (p,q) – граф, есть система объектов. G=(V,E), где V={v₁, v₂,…,v_p} – множество вершин, E={ e₁=(v_i1,v_j1), e₂=(v_i2,v_j2),…, e_q=(v_iq,v_jq)}i_k ? j_k k=1,2,3,..,q – множество неориентированных ребер ik?j1, k=1..q.

Две вершины графа G смежные (соседние), если они соединены в G ребром. Если граф G имеет ребро e=(u,v), то вершина u и ребро e (равно как и вершина v и ребро e) инцидентны (принадлежат друг другу). Изолированная вершина не инцидентна ни одному ребру. Висячая (концевая) вершина (лист) инцидентна только одному ребру. Два ребра, инцидентные одной вершине, называются смежными.

Граф G₁=(V₁,E₁) равен графу G₂=(V₂,E₂) ? V₁=V₂, E₁=E₂. Графы G₁ и G₂ изоморфны, если существует взаимнооднозначное соответствие ?: V₁?V₂, сохраняющее отношение смежности (соседства) вершин, т.е. если (u,v)?E₁ ? ((?(u),?(v))?E₂).

Граф G₁=(V₁,E₁) есть подграф графа G₂=(V₂,E₂) ? V₁ ? V₂ E₁ ? E₂. Если V₁=V₂, то подграф G₁ называется остовным подграфом графа G₂.

Подграф G₁ графа G называется порожденным множеством вершин V₁, (натянутым на множество вершин V₁), если V₁?V, и ?u,v?V₁ (e=(u,v)?E ? e ? Е₁).

Граф К_р называется полным, если каждые его 2 вершины связаны ребром. Петля, есть ребро e=(u,u). Кратные (параллельные) ребра соединяют одну и туже пару вершин.

Мультиграф допускает кратные ребра, но не допускает петель.

Песевдограф допускает и кратные ребра, и петли.

Замечание: Граф не допускает кратных ребер и петель.

Определение: Орграф (ориентированный, направленный граф) – есть граф, где все ребра ориентированны.

Замечание: также можно говорить об ориентированных мульти и псевдографах.

Спонсор:
Московский портал www.beststudent.ru позволит Вам выполнить свои курсовые, рефераты и прочие задание быстро и недорого.

1. Раскраска графов, хроматическое число и хроматический класс
2. Двудольные графы и парасочетания
3. Графы К5 и К33. Критерий планарности Понтрягина-Куратовского
4. Способы задания графов и операции над графами
5. Двудольные и бихроматические графы
6. Перечисление графов. Производящая функция для числа помеченных графов с р вершинами
7. Линейное пространство подграфов данного графа
8. Раскрашивание планарных графов. Теорема о пяти красках. Теорема о четырех красках
9. Планарные и плоские графы
10. Системы различных представителей, теорема Холла о совершенном паросочетании в двудольном графе
11. Матричная теорема Кирхгофа о деревьях
12. Верхняя и нижняя оценки для хроматического числа. Внутренне и внешне устойчивые множества вершин графа
13. Формула Эйлера
14. Обходы графа. Циклы Эйлера, Гамильтона, де Брейна
15. Деревья, их характеристика, каркасы (остовы)
16. Оптимальная раскраска вершин графа
17. Подпространство четных подграфов