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