Степень - вершина - граф
Cтраница 1
Степень вершины графа равна числу ребер, инцидентных этой вершине. Так, все вершины графа, приведенного на рис. 6.12, имеют четвертую степень, а граф, приведенный на рис. 6.13, имеет вершины различных степеней - второй и третьей. Улицы города являются примером графа - его вершины соответствуют перекресткам и тупикам, а ребра представляют части улиц, связывающие перекрестки или ведущие в тупики. В подобном графе улиц большая часть вершин имеет четвертую степень, а тупиковые улицы заканчиваются вершинами первой степени. [1]
Степенью вершины графа называют число ребер, опирающихся на эту вершину. [2]
Степенью вершины графа называется число дуг ( ребер), инцидентных этой вершине. Если граф ориентированный, то число дуг, исходящих ( заходящих) из некоторой вершины, называется полустепенъю исхода ( захода) этой вершины. [3]
 |
Полные неориентированные графы.| Исходный граф Г и дополнительный Г.| Граф Г - плоский, а граф Г2 - неплоский. [4] |
Степенью вершины графа называется количество ребер, инцидентных данной вершине. Вершина графа, имеющая степень 0, называется изолированной, а если степень ее равна 1, то такая вершина называется висячей. [5]
Если наибольшая из степеней вершин графа G равна р, то этот граф ( р - f -) - раскрашиваем. [6]
Рассмотрим, как связано хроматическое число со степенями вершин графа. [7]
В последнем разделе настоящей главы мы рассматриваем задачу о реализации наборов целых положительных чисел наборами степеней вершин графов. Эту задачу мы будем называть проблемой ( или задачей) о наборах степеней ( вершин) графов. Она представляет собой частный случай задачи об / - факторе, относящийся к ситуации, когда заданный граф является полным. Однако имеется несколько более прямых подходов для установления фундаментального результата Эрдеша и Галлаи ( 1960), дающего характеризацию реализуемых наборов степеней, а также для получения различных обобщений этого результата. Мы также рассматриваем здесь проблему реализации набора степеней графом, обладающим совершенным паросочетанием. [8]
Пусть Я - такое отображение множества дуг в множество целых чисел, что К ( е) К ( е2) в том и только том случае, когда число дуг на грани с правой ( левой) стороны от дуги е равно числу дуг на грани с правой ( левой) стороны от дуги е2, а также когда степени вершин, являющихся началами дуг е, е2, совпадают и степени вершин графа G, являющихся концами дуг е, е2, также совпадают. [9]
Перечисление графов существенно упрощается, когда применяют достаточно простые инварианты. Распределение степеней вершин графа является первым из них. В теории графов и комбинаторике его принято называть разбиением числа 2r J ] п; на t; чисел натурального ряда. [10]
 |
Графические разбиения числа 4. [11] |
Порядок слагаемых в разбиении не существен. Такое разбиение числа 2q образуют степени вершин графа, не имеющего изолированных вершин. Для того чтобы включить в рассмотрение все графы, обобщим определение разбиения, принятое в теории чисел, допуская существование неотрицательных слагаемых. [12]
На рис. 13.1 показаны помеченный граф G и его матрица смеж-ностей А. Легко заметить, что суммы элементов матрицы А по строкам равны степеням вершин графа G. Вообще в силу соответствия, существующего между графами и матрицами, с любым теоретико-графовым понятием можно сопоставить некоторый аналог, связанный с матрицей смежностей. [13]
Получить необходимые и достаточные условия существования 3-много-гранника, каждая из вершин которого имеет заданное число смежных. Другими словами, проблема состоит в описании последовательностей, назовем их полиэдральными, являющихся степенями вершин 3-полиэдрального графа ( Sainte Marie С. [14]
Такое разграничение возможно, как правило, только для одно-маршрутных обратимых реакций, поскольку в общем случае скорости многомаршрутных реакций невозможно разделить на два слагаемых, характеризующих только скорость процесса в прямом и в обратном направлениях. Последнее видно уже из уравнения (V.95) и следует из того, что скорость реакции по каждому из маршрутов зависит от скорости ее по другим маршрутам данного базиса вследствие участия в них общих стадий. В случае одномаршрутной реакции граф ее содержит только вершины 2 - й степени и скорость процесса может быть представлена двумя необратимыми слагаемыми, описываемыми движением по графу во взаимно противоположных направлениях. Для многомаршрутных реакций степени вершин графа оказываются больше двух, и число необратимых слагаемых, на которые могла бы быть разложена скорость реакции, также превышает два. [15]
Страницы: 1 2