Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Задание 3. Унарные операции над графами.
|
|
| Данаматрица смежности орграфа G 1: |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
| Необходимовыполнить операции: | - дополнения; - удаление вершины xi; - удаление дуги ai; - отождествление вершин xi и xj; - стягивание дуги ai. | ||||||||||||||||||||||||||||||||||||||||||||||||||||
Дополнением графа G = (X, A 1) является граф 
= (X, A 2), у которого множество вершин совпадает с множеством вершин графа G, а множество ребер, не принадлежит графу G, т. е. в 
любые две вершины смежны, если только они не смежны в G.
| Дополнение графа удобно находить с помощью матрицы смежности. |
|
Удаление вершины. Если xi – вершина графа G = (X, A), то xi является графом, получившимся после удаления из графа G вершины xi и всех ребер, инцидентных этой вершине. Выполним операцию удаление вершины x 5: G - x 5.
| 
|
| G | G - x 5 |
Удаление ребра или удаление дуги.
Если ai – ребро графа G = (X, A), то G - ai является графом, получающимся после удаления из G ребра ai. Заметим, что концевые вершины ребра ai не удаляются.
|
| 
|
| G | G -(x 4, x 3) |
|
|