![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
МаршрутСтр 1 из 3Следующая ⇒
Определение Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными. Смежность Две вершины называются смежными, если они соединены ребром. Два ребра называются смежными, если они имеют общую вершину. Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину. Диаграмма Диаграмма – это один из видов представления графа. Суть метода заключается в визуальном представлении графа. Изображение заключается в представлении на плоскости совокупности точек (вершин) и связывающих их линий (дуг). Маршрут Путь в графе — последовательность вершин, имеющая для каждой вершины ребро, соединяющее её со следующей вершиной в последовательности. Путь = ориентированный маршрут. Длина маршрута (пути)– количество ребер (дуг) маршрута (пути). Вес маршрута (пути) –сумма весов ребер (дуг) маршрута (пути). Замкнутый маршрут (замкнутый путь)– маршрут (путь), у которого первая и последняя вершины совпадают. Простой маршрут (простой путь) –маршрут (путь) без повторяющихся вершин. Цепь (орцепь) –маршрут (путь), в котором ребра (дуги) проходятся один раз. Простая цепь (простая орцепь) –цепь (орцепь) без повторяющихся вершин. Петля– цепь (орцепь), содержащая один узел и одно ребро (одну дугу). Связность Неориентированный граф считается связным, если из любой вершины есть путь в любую другую вершину (путь может состоять из любого количества рёбер). Чтобы граф сnвершинами был связным, он должен иметь не менее (n-1) рёбер. Если граф имеет не менее(n*n - 3n + 4)/2рёбер, то он гарантированно связный. Если граф связный, у него обязательно есть вершины степени не менее 2, то есть вершины, каждая из которых имеет не менее двух смежных вершин. Если граф связный и без циклов (то есть это дерево), то удаление любого ребра приведёт к потере связности. Несвязный граф состоит из компонент связности. Компонента связности - множество вершин такое, что из любой вершину этого множества есть путь в любую другую вершину этого множества, но ни из какой вершины этого множества нельзя попасть в некоторую вершину вне этого множества. Очевидно, что сумма количеств вершин компонент связности равна количеству вершин графа. Как определить, является ли граф связным? Выбираем некоторую вершину A и помечаем её как посещённую (1), остальные соответственно полагаются ещё не посещёнными (0): A полагаем текущей вершиной. Дальше действуем следующим образом. Пометка непосещённых смежных вершин: для текущей вершины ищем смежные с ней, ещё не непосещённые, и помечаем их как посещённые. Пусть у нас оказалось k новопомеченных вершин (на рисунке чуть выше их 3). По очереди выбираем одну из них текущей и рекурсивно выполняем пометку непосещённых смежных с ней вершин. Для текущей вершины не выполняется рекурсия, если у данной вершины нет смежных вершин, которые всё ещё не помечены как посещённые.
16)
|