Cтраница 1
Ориентированный псевдограф называется сильно связным ( или сильным), если любая вершина в нем достижима из всякой другой его вершины. Ориентированный псевдограф называется односторонне связным ( или односторонним), если для любых двух различных его вершин по меньшей мере одна достижима из другой. Ориентированный псевдограф G ( V, X) называется слабо связным ( или слабым), если ассоциированный с ним псевдограф ( V, Х) является связным. Если ориентированный псевдограф не является даже слабо связным, то он называется несвязным. Тривиальный орграф, состоящий лишь из одной вершины, считается ( по определению) сильно связным. [1]
Ориентированный псевдограф называется полным, если в нем любые две различные вершины соединены хотя бы одной дугой. Турниром называется полный направленный граф. Орграф G называется растущим деревом, если ассоциированный с ним граф является деревом и если в G есть источник. [2]
Ориентированным мулътиграфом называется ориентированный псевдограф, не содержащий петель. [3]
Доказать, что ориентированный псевдограф, имеющий не менее 2 вершин, сильно связен тогда и только тогда, когда в нем существует ориентированный остовный замкнутый маршрут. [4]
Пусть G - слабо связный ориентированный псевдограф, не являющийся односторонним. Доказать, что в G не существует такой вершины, удаление которой дает сильно связный псевдограф. [5]
Доказать, что если ориентированный псевдограф G не является сильно связным, то он будет односторонним тогда и только тогда, когда его конденсация G имеет ориентированную остовную цепь. [6]
Гамилътоновым контуром называется остовный контур ориентированного псевдографа. Если ориентированный псевдограф содержит гамильтонов контур, то сам псевдограф также называется гамилътоновым. [7]
Доказать, что в конденсации G произвольного ориентированного псевдографа G контуры отсутствуют. [8]
Доказать, что если полустепень исхода каждой вершины ориентированного псевдографа положительна, то в нем существует ориентированный цикл. [9]
Операции удаления вершины и дуги, а также понятия подграфа, остовного подграфа и порожденного подграфа определяются для ориентированных псевдографов аналогично тому, как это делалось в случае неориентированных псевдографов. [10]
Ориентированный псевдограф называется сильно связным ( или сильным), если любая вершина в нем достижима из всякой другой его вершины. Ориентированный псевдограф называется односторонне связным ( или односторонним), если для любых двух различных его вершин по меньшей мере одна достижима из другой. Ориентированный псевдограф G ( V, X) называется слабо связным ( или слабым), если ассоциированный с ним псевдограф ( V, Х) является связным. Если ориентированный псевдограф не является даже слабо связным, то он называется несвязным. Тривиальный орграф, состоящий лишь из одной вершины, считается ( по определению) сильно связным. [11]
Гамилътоновым контуром называется остовный контур ориентированного псевдографа. Если ориентированный псевдограф содержит гамильтонов контур, то сам псевдограф также называется гамилътоновым. [12]
Ориентированный псевдограф называется сильно связным ( или сильным), если любая вершина в нем достижима из всякой другой его вершины. Ориентированный псевдограф называется односторонне связным ( или односторонним), если для любых двух различных его вершин по меньшей мере одна достижима из другой. Ориентированный псевдограф G ( V, X) называется слабо связным ( или слабым), если ассоциированный с ним псевдограф ( V, Х) является связным. Если ориентированный псевдограф не является даже слабо связным, то он называется несвязным. Тривиальный орграф, состоящий лишь из одной вершины, считается ( по определению) сильно связным. [13]
Ориентированный псевдограф называется сильно связным ( или сильным), если любая вершина в нем достижима из всякой другой его вершины. Ориентированный псевдограф называется односторонне связным ( или односторонним), если для любых двух различных его вершин по меньшей мере одна достижима из другой. Ориентированный псевдограф G ( V, X) называется слабо связным ( или слабым), если ассоциированный с ним псевдограф ( V, Х) является связным. Если ориентированный псевдограф не является даже слабо связным, то он называется несвязным. Тривиальный орграф, состоящий лишь из одной вершины, считается ( по определению) сильно связным. [14]