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