Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Билет 34.

Типы графов.

Транспонированный граф – получен из исходного путём изменения направления всех дуг на противоположное. Симметричный граф – для любых i,j для (xi,xj) существует xj,xi симметрично относительно диагонали. Если для xi,xj существует хотябы 1 путь\\маршрут их соединяющий, то граф – связный. Если существует путь из xi в xj и из

xj в xi, то граф – сильно связный. Граф называется слабо связанным, если для не для всех пар вершин существует путь их соединяющий. Односторонне связанный, если для xi,xj существует 1 путь или из xi в xj или из xj в xi. Несвязный граф м.б. единственным образом разбит на связанные компоненты, т.е. на группы взаимосвязанных вершин т.о., что между вершинами отд. группы отстутствует взаимосвязь. Неориент. граф называется деревом, если он связный и не содержит циклов. Ориент. граф называется продеревом или ориент. деревом, растущим из корня х1, если он является деревом, а единственный путь между х1 и любой др. вершиной есть путь с началом в х1. Граф, у которого множество вершин пустое – пустой граф. Граф для которого для i Fxi=Ø. Граф называется насцщенным, если для i Fxi=X


Дата добавления: 2015-07-26; просмотров: 62 | Нарушение авторских прав


Читайте в этой же книге: Билет 1. | Билет 3. | Билет 4. | Билет 7. | Билет 10. | Билет 15. | Билет 19. | Билет 47. |
<== предыдущая страница | следующая страница ==>
Билет 30.| Билет 45.

mybiblioteka.su - 2015-2024 год. (0.006 сек.)