Спирина, М.С. Дискретная математика

а если не совпадают, то поиск данных продолжается. Впервые по­ нятие двоичного дерева ввел в III в. римский философ Порфирий. Цикломатическое число графа. Пусть задан неориентированный граф G. Дипломатическим числом графа называется число v(G) = = m(G) +c(G) - n(G), где m(G) — число его ребер; c(G) — число связных компонент графа; n(G) — число вершин. Цикломатиче­ ское число дерева равно нулю. Цикломатическое число леса равно сумме цикломатических чисел составных связных компонент — деревьев и, следовательно, тоже равно нулю. Для остальных гра­ фов цикломатические числа — положительные. Например, для полного графа К5 (имеющего пять вершин и С I = 10 ребер) цикломатическое число равно v = 10 + 1 - 5 = 6. 2.4. Способы задания графа. Изоморфные графы В математике значительно сильнее, чем в других дисциплинах, обнаружи­ вается черта организованности, стрем­ ление находить скрытый порядок во всем, что нас окружает... А. Сухотин Существуют различные способы задания графа: геометрический (рисунки, схемы, диаграммы), простое перечисление вершин и ребер, табличный. Человеку удобно работать с графом-рисунком, так как он может легко установить связь между вершинами в на­ глядном виде с помощью ребер, изображаемых непрерывными линиями. Такое геометрическое представление плоского графа на­ зывается его реализацией. Для машинной обработки удобнее за­ дать граф в алгебраической форме — перечислением (списком) вершин или ребер. Например, орграф на рис. 2.3 можно задать с помощью пар (Уи У2), (V2, V2), (V2, V3) и (Уз, У,), что соответствует дугам (г, и, t, s). При переходе от алгебраического способа к геометриче­ скому одному и тому же графу могут соответствовать различные изображения — изоморфные графы, при этом от правильного изоб­ ражения зависит, например, свойство плоской реализуемости. Для этого нужно правильно задать сам граф. Основным способом задания графа является перечисление всех его вершин и ребер. Но такое представление, во-первых, несим­ метрично (с ним трудно работать, особенно ЭВМ), во-вторых, для указания каждого ребра нужно еще раз выписывать соответ­ ствующие вершины, что плохо с точки зрения сжатия и хранения информации. Иногда граф задается таблицей, состоящей из п строк (вершины) и т столбцов (ребра). Главным во всех способах зада­ 84