2015-06-10
176Графом называется бинарное (2-арное) отношение на множестве элементов, называемых вершинами графа. Вершины соединяются дугой (изображается на рисунках стрелкой), если соответствующая упорядоченная пара входит в отношение. Обратите внимание, что исходящая вершина (из которой стрелка выходит) является первой в паре.
Граф называется неориентированным, если стрелки-дуги не имеют направления. В этом случае дуги называются ребрами графа.
Граф называется ориентированным, если все его дуги ориентированы (т.е. имеют исходящую и входящую вершины).
Из определения графа как отношения непосредственно следует естественный способ описания графа в виде матрицы (таблицы) смежности. (Таблица есть отношение.) Матрица квадратная, т.е. числа строк и столбцов совпадают. 1 означает наличие отношения, 0 – отсутствие. Обратите внимание, что номер исходящей вершины
Графы применяются для наглядного изображения бинарных отношений. Этот способ удобен человеку для восприятия таких отношений. Компьютеры же «предпочитают» табличный способ описания отношений. Поэтому мы здесь описываем оба эти способа.
|
|
|
Оба способа дают компактное и наглядное представление об отношениях рассматриваемых элементов (вершин). Многие отчетные данные педагога просят представлять в виде графов. Графы также являются эффективным приемом обеспечения наглядности представления информации в учебном процессе. Владение этими средствами наглядности и программными инструментами, облегчающими их построение — важная компонента компетентности современного учителя.
Пример.
Отношение R – строго меньше на множестве 3 первых натуральных чисел.
Матрица смежности:
Граф:
Для наглядности дуги графа помечены теми же цветами, что и соответствующие им элементы матрицы.
