Cтраница 4
Подграфом данного графа называют его часть, состоящую из некоторых его ребер. Дополнением подграфа называется вся остальная часть рассматриваемого графа. Связный граф или подграф, в котором каждая вершина инцидентна только двум ребрам, называют контуром. Следовательно, ребра контура образуют замкнутый путь. [46]
Подграфом полного графа называется любой граф, содержащийся в полном графе в том смысле, что все вершины и ребра подграфа принадлежат полному графу. Нетрудно видеть, что любой полный граф является подграфом любого полного графа с большим числом вершин. Многие простые графы имеют свои собственные названия. На рис. 108 представлены четыре семейства графов: маршруты, циклы, звезды и колеса. [47]
Механическая цепь ( а и ее граф, представленный в двух конфигурациях ( б и в. [48] |
Подграфом данного графа называют его часть, состоящую из некоторых его ребер. Дополнением подграфа называется вся остальная часть рассматриваемого графа. Связный граф или подграф, в котором каждая вершина инцидентна только двум ребрам, называют контуром. Следовательно, ребра контура образуют замкнутый путь. [49]
Двудольным информационным подграфом к-разрывов называют подграф, состоящий из к вершин типа / и к вершин типа z, удаление которого из исходного двудольного графа. Возможность получения ациклического информационного графа определяют по алгоритмам, разработанным на основе операций преобразования структуры двудольных информационных графов. [50]
Если подграф С - Т имеет компоненту Н типа I, то она совпадает с ним. [51]
Найти подграф Куратовского ( 1) в графе Петерсена и ( И) в графе, который получается из графа куба посредством соединения двух противоположных вершин одним новым ребром. [52]
Такой подграф называется сильной компонентой графа G. Аналогично, односторонняя компонента представляет собой односторонний максимальный подграф, а слабая компонента - максимальный слабый подграф. [53]
Эти подграфы называются связными компонентами графа G. Таким образом, мы получаем следующее утверждение. [54]