Представление - граф
Cтраница 2
Наиболее известный способ представления графа на бумаге состоит в геометрическом изображении точек и линий. В ЭВМ граф должен быть представлен дискретным способом, причем возможно много различных представлений. [16]
Еще одни способ представления графа - связать с каждой, вершиной список смежных с ней вершин. В этой случае граф превращается в список пар, каждая из которых состоит из вершины плюс ее список смежности. [17]
Есть разные способы представления графов. Для человека наиболее удобны рисунки ( по крайней мере в тех случаях, когда граф не слишком велик), но для машинной обработки более приемлемы иные формы представления. Опишем две из них, в основе которых лежит изображение графа в виде матрицы с произвольной нумерацией вершин и ребер. Если в графе G нет петель, то в каждом столбце матрицы М будет ровно две единицы. Наличие столбца с одной единицей означает, что в графе имеется петля; параллельные ( кратные) ребра соответствуют одинаковым столбцам. [18]
 |
Граф с гамильтоновым циклом ( изображен зачерненными линиями. Существует только один гамильтонов цикл, как читатель может сам убедиться. [19] |
Есть разные способы представления графов на языке двоичных чисел. Неважно, какой из этих способов применяется в том или ином случае. [20]
G, называется интервальным представлением графа G. [21]
Из рассмотренного там способа представления графа в памяти машины видно, что информация о связях какой-либо вершины графа с другими его вершинами задавалась как раз в виде записи, отдельными компонентами которой были ссылки на соответствующие вершины графа. [22]
В теории графов классическим способом представления графа служит матрица ищиденций. [23]
Наиболее известный и популярный способ представления графов состоит в геометрическом изображении точек ( вершин) и линий ( ребер) на бумаге. При численном решении задач на вычислительных машинах граф должен быть представлен дискретным способом. Существует довольно много способов такого рода представления графов. Однако простота использования представления графа, как и эффективность алгоритма, в основе которого он лежит, в полной мере зависит от конкретного выбора этого представления. Одно из направлений теории графов связано с их матричным представлением. Существуют различные виды матриц, ассоциированные с графами. Эти алгебраические формы используются для решения многих задач теории графов. Ниже рассматриваются две такие матричные формы и несколько нестандартных представлений, которые наиболее широко используются в алгоритмах на графах. [24]
Определение этого отношения зависит от способа представления графа. [25]
Тогда векторы v / w / образуют ортонормированное представление графа 0 оЯ ( это следует из включения G-Яз G-Я и того. [26]
Написать процедуры перехода между каждыми двумя способами представления графа, описанными в разд. [27]
Какие функции выполняют линии и точки при представлении графа. [28]
Напишите подробный алгоритм обхода в глубину, использующий представление графа с помощью матрицы примыканий; при посещении очередной вершины алгоритм должен просто печатать ее метку. Проверьте алгоритм на примерах графов, приведенных в этом разделе, и убедитесь, что он дает те же результаты. [29]
Напишите подробный алгоритм обхода по уровням, использующий представление графа с помощью матрицы примыканий; при посещении очередной вершины алгоритм должен просто печатать ее метку. Проверьте алгоритм на примерах графов, приведенных в этом разделе, и убедитесь, что он дает те же результаты. [30]
Страницы: 1 2 3 4