Дискретная математика. Используя способность к обобщению, анализу и восприятию информации, дайте определение ориентированным и неориентированным графам
 Скачать 15.12 Kb.
|
|
Тема: Используя способность к обобщению, анализу и восприятию информации, дайте определение ориентированным и неориентированным графам Многие объекты, возникающие в жизни человека, могут быть смоделированы (представлены в памяти компьютера) при помощи графов. Например, транспортные схемы (схема метрополитена и т. д.) изображают в виде станций, соединенных линиями. В терминах графов станции называются вершинами графа а линии – ребра. Графом называется конечное множество вершин и множество ребер. Каждому ребру сопоставлены две вершины – концы ребра. Бывают различные варианты определения графа. В данном определении концы у каждого ребра – равноправны. В этом случае нет разницы где начало, а где – конец у ребра. Но, например, в транспортных сетях бывают случаи одностороннего движения по ребру, тогда говорят об ориентированном графе – графе, у ребер которого одна вершина считается начальной, а другая – конечной. Ориентированный граф — это граф, на всех ребрах которого выбрано одно из двух направлений. Ребра в ориентированном графе часто называют дугами. Ориентированные графы могут моделировать транспортные сети, стадии в изготовлении того или иного продукта, логическую последовательность в изучении какого-либо предмета, и так далее. Если некоторое ребро u соединяет две вершины A и B графа, то говорят, что ребро u инцидентно вершинам A и B, а вершины в свою очередь инцидентны ребру u. Вершины, соединенные ребром, также называют смежными. Два ребра называются кратными, если они соединяют одну и ту же пару вершин. Ребро называется петлей, если его концы совпадают. Степенью вершины называют количество ребер, для которых она является концевой (при этом петли считают дважды). Во многих задачах кратные ребра и петли не представляют интереса, поэтому могут рассматриваться только графы без петель и кратных ребер. Такие графы называю простыми. Легко понять, что сумма степеней всех вершин равна удвоенному числу ребер в графе. Отсюда можно посчитать максимальное число ребер в простом графе: если у графа n вершин, то степень каждой из них равна n−1, а, значит, число ребер есть n(n−1)/2. Граф, в котором любые две вершины соединены одним ребром, называется полным графом. Также легко заметить следующий факт: в любом графе число вершин нечетной степени – четно. Этот факт называется «леммой о рукопожатиях» – в любой компании число людей, сделавших нечетное число рукопожатий всегда четно. Часто рассматриваются графы, в которых каждому ребру приписана некоторая числовая характеристика — вес. Вес может означать длину дороги или стоимость проезда по данному маршруту. Соответствующие графы называются взвешенными. Многие объекты, возникающие в жизни человека, могут быть смоделированы (представлены в памяти компьютера) при помощи графов. Например, транспортные схемы (схема метрополитена и т. д.) изображают в виде станций, соединенных линиями. В терминах графов станции называются вершинами графа а линии – ребра. Графом называется конечное множество вершин и множество ребер. Каждому ребру сопоставлены две вершины – концы ребра. Бывают различные варианты определения графа. В данном определении концы у каждого ребра – равноправны. В этом случае нет разницы где начало, а где – конец у ребра. Но, например, в транспортных сетях бывают случаи одностороннего движения по ребру, тогда говорят об ориентированном графе – графе, у ребер которого одна вершина считается начальной, а другая – конечной. Если некоторое ребро u соединяет две вершины A и B графа, то говорят, что ребро u инцидентно вершинам A и B, а вершины в свою очередь инцидентны ребру u. Вершины, соединенные ребром, называются смежными. Ребра называются кратными, если они соединяют одну и ту же пару вершин (а в случае ориентированного графа – если у них совпадают начала и концы). Ребро называется петлей, если у него совпадают начало и конец. Во многих задачах кратные ребра и петли не представляют интереса, поэтому могут рассматриваться только графы без петель и кратных ребер. Такие графы называю простыми. Иногда граф рассматривают без учета ориентации дуг, тогда его называют неориентированным графом. Понятие “дуга”, “путь” и “контур" для неориентированного графа заменяются понятиями “ребро”, “цепь”, “цикл”. Ребро - это отрезок, соединяющий 2 вершины. Цепь - последовательность ребер. Цикл - цепь, у которой начальная и конечная вершины совпадают. Описать неориентированный граф можно путем задания пары множеств (Х,U), где Х - множество вершин; U - множество ребер. Однако более удобным является описание неориентированного графа с помощью матрицы смежности или инцидентности, которые строятся аналогично соответствующим матрицам для ориентированных графов с той разницей, что не делается различия между заходящей в вершину и исходящей из нее дугами. При этом вершины х и y называют смежными, если существует соединяющее их ребро, а само это ребро называется инцидентным вершинам х и у. Степенью вершины в неориентированном графе называется число инцидентных данной вершине ребер (при этом петля считается два раза, то есть степень - это количество «концов» ребер, входящих в вершину). Довольно очевидно, что сумма степеней всех вершин равна удвоенному числу ребер в графе. Отсюда можно посчитать максимальное число ребер в простом графе - если у графа n вершин, то степень каждой из них равна n−1, а, значит, число ребер есть n(n−1)/2. Граф, в котором любые две вершины соединены одним ребром, называется полным графом. Также легко заметить следующий факт – в любом графе число вершин нечетной степени – четно. Этот факт называется «леммой о рукопожатиях» – в любой компании число людей, сделавших нечетное число рукопожатий всегда четно. |