Связная графа
Cтраница 1
Связные графы, которые имеют разрезы, состоящие из одного ребра, могут быть описаны в терминах циклов. [1]
Связные графы могут быть перечислены в терминах полного числа графов комбинаторным методом, который аналогичен перечислению корневых деревьев в терминах этих деревьев, как это сделано у Пойа. [2]
Некоторые связные графы можно сделать несвязными, удалив одну вершину, которая называется точкой сочленения. Выделение таких вершин сильно помогает в изучении структуры связного графа. Ребра с аналогичным свойством называются мостами. После определения этих трех понятий будут введены и изучены два новых графа, связанных с данным графом - граф его блоков и граф его точек сочленения. [3]
Найти связные графы, удовлетворяющие ( 13.4 Л) и имеющие минимальное число ребер. [4]
 |
Разделимый граф ( а, набор его блоков ( б, листьев ( в и листовая композиция ( г. [. [5] |
Существуют связные графы, которые можно сделать несвязными удалением некоторых элементов. Вершина, удаление которой ( вместе с инцидентными ей ребрами) увеличивает число компонент графа, называется точкой сочленения. Ребро с аналогичным свойством называется мостом. Остальные ребра графа являются циклическими ( входят хотя бы в один цикл), к ним относятся также петли в псевдографах. Связный граф с точками сочленения называется разделимым. Произвольный граф можно разбить на блоки, каждый из которых представляет собой максимальный неразделимый подграф. Блоки в графе соединены только в точках сочленения. Там же изображены листья этого графа, на которые он разбивается после удаления всех его мостов. Каждый лист, за исключением тривиального, очевидно, является максимальным подграфом, представляющим собой связное множество циклических ребер. Тривиальный лист состоит из одной вершины. Листовой композицией называется граф, получаемый из исходного стягиванием в единственную вершину всех вершин одного листа. Таким образом, вершины листовой композиции изображают листья, а ее ребра - мосты исходного графа. [6]
Найти связные графы, удовлетворяющие (13.4.1) и имеющие минимальное число ребер. [7]
На сильно связных графах определяется интересная мера, называемая индексом центральности. Она характеризует степень разброса вершин графа. [8]
На сильно связных графах типа И / ИЛИ с числом вершин не более 20 процессорное время работы программы не превышает 1 мин. [9]
Построить все топологически неэквивалентные связные графы, имеющие точно по четыре ребра. [10]
Нас также будут интересовать связные графы, в которых существует одна и только одна цепь, соединяющая каждую пару вершин; такие графы называются деревьями ( по аналогии с генеалогическими деревьями) и рассматриваются в гл. [11]
Установим несколько общих теорем о связных графах и подграфах. [12]
Сначала отметим, что достаточно рассматривать связные графы. Связный граф, каждая вершина которого имеет четную степень, содержит эйлеров цикл. Значит, такой цикл есть и в нашем графе. [13]
Теорема 8.3. Пусть G и G - связные графы, у которых реберные графы изоморфны. [14]
Mizuno ( 84, 4B499 ] изучают связные графы ее ( степени 1) вершин. [15]
Страницы: 1 2 3 4