Главная » Учебно-методические материалы » ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ » Математические методы. Попова Н.В. |
22.12.2011, 14:28 | ||||
Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными. Граф Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 2.15). Рис. 2.15 Петля это дуга, начальная и конечная вершина которой совпадают. Простой граф граф без кратных ребер и петель. Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер. Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные. ПУТИ, МАРШРУТЫ, ЦЕПИ и ЦИКЛЫ. Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути. Маршрут в графе путь, ориентацией дуг которого можно пренебречь. Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом. Граф отношения делимости Построим граф, изображающий отношение делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на первое (рис. 2.16). Рис. 2.16 ПОДГРАФЫ Подграф графа это граф, являющийся подмоделью исходного графа, т.е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф). Подграф, порожденный множеством вершин U это подграф, множество вершин которого - U, содержащий те и только те ребра, оба конца которых входят в U. Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа. Связность графа Граф называется связным, если любая пара его вершин связана. Деревья Дерево — это связный граф без циклов. Генеалогическое дерево На рисунке 2.17 показано библейское генеалогическое дерево. Рис. 2.17 Граф без цикла называется лесом. Вершины степени 1 в дереве называются листьями. Очевидно, что графический способ представления графов непригоден для ПК. Поэтому существуют другие способы представления графов. В теории графов применяются
Составим матрицы инциндентности и смежности для следующего непрерывного графа (рис. 2.18)
| http://matmetod-popova.narod.ru/ |