Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Элементы теории графов
|
|
 | |||
 | |||
|
|
|
|
|
|
Структура изображённая на рисунке – граф.
Граф задаётся двумя множествами G=(x,u), непустым множеством, х не равен 0; множеством вершин x={x1; x2; x3; x4; x5; x6; x7}; или множеством пар элементов u={ x1x1; x1x2; x2x3; x3x4; x3x5; x4x5; x5x6}
При этом элементы множества Uмогут повторяться, а так же могут повторяться элементы в парах.
Граф заданный на множествах «x» и«u» обозначается G=(x,u).
Если элементы в парах не упорядочены (не указано направление), то граф называется неориентированным графом, в противном случае – ориентированным графом или орграфом.
Элементы множества Х называются вершинамиграфа, а элементы множества U называются рёбрами для неориентированного графа и дугами для ориентированного.
На плоскости граф задаётся в виде плоскостей и вершин и линий соединяющих вершины или некоторые из них.
1. Определение для неориентированного графа: ребро, начало и конец которого совпадают, называется петлёй (x1x1)
2. Вершины называются смежными или соседскими, если существует ребро их соединяющее.
3. Если вершина является началом или концом ребра, то эти вершины и ребро называются инцидентными.
4. Степенью вершины называется число инцидентных её рёбер
5. Вершина, степень которой равна 0, называется изолированной (x7)
6. Вершина, степень которой равна 1, называется висячей или тупиковой. (x6)
7. Последовательность вершин и рёбер, в которой конец предыдущего ребра совпадает с началом следующего, называется маршрутом. Число рёбер маршрута определяет его длину.
8. Цепью называется маршрут, в котором все рёбра различны.
9. Граф называется связным, если для двух любых его вершин существует цепь, их соединяющая.
10. Расстоянием между вершинами связного графа называется длина самой короткой цепи, соединяющей его вершины
11. Диаметром графа называется максимальное расстояние между его вершинами.
12. Циклом называется цепь, начало и конец которой совпадают (x3; x4; x5; x3). Простым циклом называется простая цепь
13. Цикл в графе называется Эйлеровым, если он содержит все рёбра графа только один раз.
14. Связный граф, в котором есть Эйлеров цикл называется Эйлеровым графом (его можно нарисовать не отрывая руки от листа)
Теорема: связный граф называется Эйлеровым тогда и только тогда, когда степень каждой его вершины чётная.
15. Подграфом графа G=(x,u) называется такой граф G=(x1,u1), для которого x1входит в множество х, а u1входит в множество u
16. Компонентой связности графа называется его связный граф не являющийся собственным подграфом никакого другого связного подграфа данного графа. (Компонента связности графа – это некоторое множество вершин графа, такое, что для любых двух вершин из этого множества существует путь из одной в другую и не существует пути из вершин этого множества в вершины не из этого множества)
Date: 2015-07-17; view: 324; Нарушение авторских прав