Билет 34.

Типы графов.

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

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

Дата добавления: 2015-07-26