Теоретическая часть: задача раскраски графов и ее приложения
Вершины и рёбра графа называются также элементами графа, число вершин в графе — порядком, число рёбер — размером графа. Вершины и называются концевыми вершинами (или просто концами) ребра. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними. Два ребра называются смежными, если они имеют общую концевую вершину. Ребро называется петлёй… Читать ещё >
Теоретическая часть: задача раскраски графов и ее приложения (реферат, курсовая, диплом, контрольная)
Основные определения
Граф, или неориентированный граф G — это упорядоченная пара G=G (V, E), для которой выполнены следующие условия:
- 1. V — это непустое множество вершин, или узлов,
- 2. E — это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.
Вершины и рёбра графа называются также элементами графа, число вершин в графе — порядком, число рёбер — размером графа. Вершины и называются концевыми вершинами (или просто концами) ребра. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними. Два ребра называются смежными, если они имеют общую концевую вершину.
Ребро называется петлёй, если его концы совпадают, то есть Степень вершины — это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.
Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой). Помимо этого, в теории графов рассматриваются мультиграфы — это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами. Маршрут в графе — это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней. Путь в графе (иногда говорят простой путь) — это маршрут без повторения вершин (а значит, и ребер). Контур — это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней. Последовательности вершин (рис. 1): 1−2-3−4-2−5 не простой путь, а маршрут; последовательности 1−2-3−4-7−5 и 1−2-5 — простые пути; 1−2-3−4-2−5-6−1 -это цикл (но не контур); 1−2-5−6-1 — это контур.