Cтраница 2
Подграф, содержащий только те вершины графа, которые одновременно достижимы из одной вершины на графе и из другой вершины на обратном графе, и дуги между этими вершинами, назовем псевдокомпонентой связности двух различных вершин ориентированного графа. [16]
Подграфы этих путей изображены на тех же рисунках. [17]
Подграф, образованный удалением из графа минимального количества ветвей таким образом, что разрушаются все контуры, но сохраняются все узлы, называют деревом графа. [18]
Подграф, являющийся полным ( пустым) графом, такой, что любой включающий его подграф исходного графа не является полным ( пустым), называется максимальным полным ( пустым) подграфом. Наибольший связный подграф несвязного графа называется компонентом связности. Подграф, являющийся деревом и включающий в себя все вершины исходного графа, называется остовом. Число ребер, не вошедших в остов, называется цикломатическим числом. Цикл в графе G ( X, U), длина которого равна Х, называется гамильто-новым циклом, а граф, в котором такой цикл существует, - гамильто-новым графом. [19]
Подграфы этих путей изображены на тех же рисунках. [20]
Вершины сигнального графа ( а. сигнальные графы, соответствующие первому ( б, второму ( в, третьему ( г ц четвертому ( д уравнениям. сигнальный граф системы уравнений в целом ( е. [21] |
Подграф, отвечающий последнему равенству, показан на рнс. [22]
Подграф, имеющий одну начальную вершину и не более одной конечной, называется гамаком [7], если в множестве предшественников начальной вершины подграфа не содержится конечная. [23]
Преобразование графов. а - параллельное соединение. б - пря. [24] |
Подграф, получающийся при удалении дуг и вершин г-го прямого пути, а также всех дуг, выходящих и входящих в удаляющиеся вершины, называется подграфом г-го прямого пути. [25]
Подграфы Я и / С графа С называются непересекающимися, если они не имеют ни общих ребер, ни общих вершин. Аналогичная символическая запись существует и для условия, что граф С не является пустым: 0 с: О. [26]
Подграф соединяется с остальной частью графа в так называемых соединяющих вершинах. В настоящем разделе мы дадим формальное определение таких вершин, введем соответствующие обозначения и докажем несколько теорем. [27]
Подграф Я графа О будем называть обособленным в О, если в нем нет вершин, являющихся соединяющими для него в графе О. Таким образом, и сам граф С, и его пустой подграф - обособленные подграфы в О. [28]
Компоненты Г ( Ц циклически-реберной связности графа. Компоненты Г ( Ц связности графа. Компоненты Г ( Ц с Г ( Ц связаны мостами. [29] |
Подграф F ( L), определяемый листовым множеством L, называется листом. [30]