2015-06-28
469
Пусть v1, v2 – вершины, е1 – соединяющее их ребро. Тогда вершина v1 и ребро е1 – инцидентны, вершина v2 и ребро е1 также инцидентны. Два ребра инцидентные одной вершине (е1,е2 инцидентны v2) называются смежными. А также две вершины инцидентные одному ребру (v1, v2 инцидентны е1 называются смежными.
Пример: обычно граф изображают диаграммой: вершины – точками (или кружками), ребра – линиями. Изобразим граф, имеющий 4 вершины и 5 ребер.
 |
Пример: Задание: выписать все смежные и несмежные вершины и ребра.
Решение:
Таб.7
| Смежные вершины | Несмежные вершины | Смежные ребра | Несмежные ребра |
| v1и v2 | v1 и v3 | e1 и е2 | e1 и е3 |
| v2 и v3 | e2 и е3 | e4 и е2 | |
| v3 и v4 | e3 и е4 | ||
| v4 и v1 | e4 и е1 | ||
| v4 и v2 | e4 и е5 | ||
| e3 и е5 | |||
| e1 и е5 | |||
| e2 и е5 |
До настоящего момента мы рассматривали неориентированный граф. Если каждому ребру графа присвоить направление (в виде стрелочки) от одной вершины к другой, то такие ребра называются дугами, а содержащий их граф называется ориентированным (или орграфом).
Первая по порядку вершина инцидентная дуге ориентированного графа, называется его началом, вторая – его концом.
Вершины в ориентированном графе называются узлами.
Рассмотрим некоторые виды графов:
· Если ребро соединяет вершину саму с собой, то такой элемент графа называется петлей, а содержащий его граф называется графом с петлей (или псевдографом):
 |
· Если различные ребра могут быть инцидентными одной паре вершин, то они называются кратными, а содержащий их граф называется мультиграфом:
 |
· Множество ребер Е может быть пустым:
 |
· Линии, изображающие ребра графа могут пересекаться, но точки пересечения не являются вершинами:
·
 | |||
 | |||
· Граф может быть бесконечным:
Каждому неориентированному графу можно поставить в соответствие орграф с тем же множеством вершин заменив лишь ребра неориентированного графа на направленные дуги орграфа. Такое соответствие называется каноническим.
