Графы.
Математика для педагогических специальностей
Каждому ребру соответствует пара точек. Эта пара точек может быть упорядоченной или нет. В том случае, когда пары точек упорядочены, говорят, что ребра ориентированы, это обычно показывают стрелками, тогда они называются дугами, и граф с такими ребрами называется ориентированным графом. Определение 1.4. Путь — это последовательность дуг (в ориентированном графе) или ребер (в неориентрированном… Читать ещё >
Графы. Математика для педагогических специальностей (реферат, курсовая, диплом, контрольная)
Еще один способ графического представления информации — это граф.
Определение 1.3. Граф — это множество точек и множество линий, соединяющих между собой все или часть этих точек.
Точки называют вершинами графа, а линии, соединяющие вершины, — ребрами графа. Вершины и ребра графа называются также элементами графа, число вершин в графе — порядком, число ребер — размером графа.
Вершины, прилегающие к одному и тому же ребру, называются смежными.
Каждому ребру соответствует пара точек. Эта пара точек может быть упорядоченной или нет. В том случае, когда пары точек упорядочены, говорят, что ребра ориентированы, это обычно показывают стрелками, тогда они называются дугами, и граф с такими ребрами называется ориентированным графом.
Если ребра не имеют ориентации, т. е. пары точек неупорядочены, граф называется неориентированным.
Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра — линиями, соединяющими точки (рис. 1.15, 1.16).
Рис. 1.15. Пример неориентированного графа.
Рис. 1.16. Пример ориентированного графа.
Пустым называется граф без ребер (рис. 1.17). Полным называется граф, в котором каждые две вершины смежные (рис. 1.18).
Рис. 1.17. Пустой граф.
Рис. 1.18. Полный граф.
Точки на графе являются изображением, как правило, однотипных объектов (множество населенных пунктов, множество людей, множество книг и т. д.). Объекты графа обычно обозначаются Vn. Связь между объектами (ребра графа) — пара точек — обозначается Ет. Дуги обозначаются Ак. Неориентированный граф обозначается G — (V, Е), ориентированный граф — G = (V, A).
Определение 1.4. Путь — это последовательность дуг (в ориентированном графе) или ребер (в неориентрированном графе), в которой конечная вершина всякой дуги (ребра), отличной от последней, является начальной вершиной следующей дуги (ребра).
Определение 1.5. Маршрут is неориентированном графе — это последовательность ребер, в которой конечная вершина всякого ребра, отличного от последнего, является начальной вершиной следующего. Цепью в называется маршрут без повторяющихся ребер. Циклом называют цепь, в которой первая и последняя вершины совпадают.
Связным называется граф, в котором каждые две вершины соединены путем (рис. 1.19).
Рис. 1.19. Связный граф.
Деревом называется связный граф без циклов.