И код направления подготовки
жүктеу/скачать 341.63 Kb.
|
- Бұл бет үшін навигация:
- Определение.
- Части графов, связность и числа графов. Деревья.
| Определение. 1) Неориентированным графом G=(V,X) называется пара множеств: V – множество, элементы которого называются вершинами, X – множество неупорядоченных пар вершин, называемых ребрами. Если v, w V, x=(v,w)X, то говорят, что ребро x соединяет вершины v и w или ребро x инцидентно вершинам v и w. Таким образом, {v,w} – обозначение ребра.
2) Если Х представляет собой упорядоченные пары (т. Е. X – подмножество декартова произведения V×V), то граф называется ориентированным, а пары (v,w) называют дугами. 3) Если множеству X принадлежат пары v=w, то такие ребра {v,v} (дуги (v,v)) называют петлями. Существование одинаковых пар {v,w} ((v,w)) соответствует наличию параллельных или кратных ребер (дуг), а кратностью ребер называют количество таких одинаковых пар. Определение. Граф называется простым, если каждую пару вершин соединяет не более, чем одно ребро. Граф называется мультиграфом, если хотя бы одну пару вершин соединяет более, чем одно ребро. Ребра мультиграфа, соединяющие одну и ту же пару вершин, называют кратными. В мультиграфе ограничений на число ребер нет. Например, кратность ребра {v1, v2} в графе, изображенном на рис. 2, равна двум, кратность ребра {v3, v4} − трем. Рис.2. Псевдограф − граф, в котором есть петли и/или кратные ребра. Мультиграф − псевдограф без петель. Граф может вовсе не иметь ребер: Е=Ø. Такой граф называется пустым, или 0-графом. Для простого графа существует другой крайний случай, когда все вершины соединены между собой ребрами. Такой граф называется полным, причем различают два вида полных графов – с петлями и без петель. Полный граф с п вершинами имеет (п2 – п)/2 ребер (формула из комбинаторики для числа сочетаний из п по 2), если петли не учитываются, и (п2 – п)/2 + п – (п2 + п)/2 ребер, если добавить п петель. Итак, используемые далее обозначения: V – множество вершин; X – множество ребер или дуг; v (или vi)– вершина или номер вершины; G, G0 – неориентированный граф; D, D0 – ориентированный; {v,w} − ребра неориентированного графа; {v,v} – обозначение петли; (v,w) − дуги в ориентированном графе; v,w – вершины, x,y,z – дуги и ребра (в мультиграфе каждое ребро (дуга) должны иметь свое собственное имя; n(G), n(D) количество вершин графа; m(G) – количество ребер, m(D) – количество дуг. Вопросы для закрепления: Что представляет собой граф? Какие виды графов бывают? Какой граф называется простым? Мультиграфом? Пустым? Полным? Литература: Основная [1] стр.155- 161, [3]стр 291-294, дополнительная [1],[2]; Интернет ресурсы [1]-[4] Тема 9 Части графов, связность и числа графов. Деревья. Количество часов 1 Основные вопросы/план темы: Части графов. Понятие подграфа, частичного графа. Связность, компоненты связности. Числа графов: цикломатическое, хроматическое, внешней и внутренней устойчивости. Деревья, свойства деревьев. Тезисы лекции*: Подграфом DA графа D называется граф, в который входит только часть вершин графа D, образующих множество А, вместе с дугами, соединяющими эти вершины. жүктеу/скачать 341.63 Kb. Достарыңызбен бөлісу:
|