Особенности применения теории графов при решении задач и в практической деятельности

курсовая работа

3. Графический или геометрический способ задания графов. Понятие смежности и инцидентности

Важнейший способ задания графа - графический. Его преимущества следует из наглядности всех элементов графа, что позволяет быстро визуально анализировать его строение. Это явное превосходство метода предопределило его широкое использование. В первую очередь это относится к тем сферам применения графов, которые связаны с передачей какой - то информации большому числу людей. Например, схемы движений различных видов транспорта, эвакуаций людей из помещений в чрезвычайных ситуациях, размещения экспозиций, выставок и т.д., даются только в графическом виде, иначе их не сможет воспринять большая масса народа, что, неизбежно, создает очевидные проблемы.

Однако у этого метода представления графов есть и свои недостатки. К ним относятся громоздкость и трудность машинного восприятия. Второе особенно важно при обработке графа с помощью ЭВМ, это в первую очередь относится к задачам управления различными отраслями народного хозяйства страны.

Поэтому в теории графов разработаны и другие способы их задания. Существует несколько достаточно удобных методов аналитического представления графов, из которых наиболее удобными считаются следующие два. Если вершина Vn является концом ребра Xn , то говорят, что они (ребро и вершина) инцидентны. В то время как смежность представляет собой отношение между однородными объектами (вершинами или ребрами или дугами)

Делись добром ;)