Любой несвязный граф является совокупностью связных графов. Эти графы обладают тем свойством, что ни- [c.259]
Графом называется совокупность двух конечных множеств множества точек (х/, Х2,. .., х ), которые называются вершинами, и множества пар вершин, которые называются ребрами (eh e2,. .., е ). Если пары вершин упорядочены, т.е. на каждом ребре задано направление, ребро называется дугой, а граф называется ориентированным, иначе — неориентированным. Последовательность ребер, ведущая от некоторой вершины к другой вершине, образует путь. Замкнутый путь называется циклом. Граф называется связным, если для любых двух вершин существует путь, их соединяющий. В противном случае граф называется несвязным. Если дугам (i, /) присвоены некоторые числа или веса (Су), то граф называется нагруженным. В ориентированном графе вершины, не имеющие входных дуг, называются начальными (источниками), а вершины, не имеющие выходных дуг - конечными (стоками), остальные -промежуточными. [c.26]
Граф G называется связным, если для любых двух его вершин существует путь, их соединяющий. В противном случае граф G называется несвязным. [c.259]
ЦИКЛОМАТИЧЕСКОЕ ЧИСЛО [ y lomati number] — термин теории графов одна из возможных числовых характеристик несвязного графа. Если граф X имеет п вершин, т ребер, а р — количество его связных частей, компонент (см. Граф), то Ц.ч. определяется равенством [c.390]
ДЕРЕВО [tree] — в теории графов связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны) если за п принять число вершин (элементов графа), то он содержит ровно п - 1 ребро, не имеет циклов если добавить ребро, соединяющее две несмежные вершины, то образуется один цикл при удалении любого ребра граф становится несвязным каждая пара вершин соединяется одной, и только одной цепью. Исходная вершина называется корнем, пути от нее [c.76]