Теория графов - основные свойства

Графы имеют различные свойства, которые используются для описания графов в зависимости от их структур. Эти свойства определены в конкретных терминах, относящихся к области теории графов. В этой главе мы обсудим несколько основных свойств, общих для всех графов.

Расстояние между двумя вершинами

Это количество ребер на кратчайшем пути между вершиной U и вершиной V. Если есть несколько путей, соединяющих две вершины, то кратчайший путь считается расстоянием между двумя вершинами.

Обозначение - d (U, V)

Может быть любое количество путей от одной вершины к другой. Среди них вам нужно выбрать только самый короткий.

Example

Взгляните на следующий график -

Здесь расстояние от вершины «d» до вершины «e» или просто «de» равно 1, так как между ними есть одно ребро. Есть много путей от вершины 'd' к вершине 'e' -

  • да, аб, быть
  • df, fg, ge
  • de (Считается за расстояние между вершинами)
  • df, fc, ca, ab, be
  • da, ac, cf, fg, ge

Эксцентриситет вершины

Максимальное расстояние между вершиной и всеми остальными вершинами считается эксцентриситетом вершины.

Обозначение - e (V)

Расстояние от конкретной вершины до всех остальных вершин в графе берется, и среди этих расстояний эксцентриситет является наивысшим из расстояний.

Example

На приведенном выше графике эксцентриситет «а» равен 3.

Расстояние от 'a' до 'b' равно 1 ('ab'),

от 'a' до 'c' равно 1 ('ac'),

от 'a' до 'd' равно 1 ('ad'),

от 'a' до 'e' равно 2 ('ab' - 'be') или ('ad' - 'de'),

от 'a' до 'f' равно 2 ('ac' - 'cf') или ('ad' - 'df'),

от 'a' до 'g' равно 3 ('ac' - 'cf' - 'fg') или ('ad' - 'df' - 'fg').

Таким образом, эксцентриситет равен 3, что является максимумом от вершины «a» от расстояния между «ag», которое является максимальным.

Другими словами,

е (б) = 3

е (с) = 3

е (г) = 2

е (е) = 3

е (е) = 3

е (г) = 3

Радиус связного графа

Минимальный эксцентриситет от всех вершин считается радиусом Графа G. Минимальное среди всех максимальных расстояний между вершиной и всеми остальными вершинами считается радиусом Графика G.

Обозначение - r (G)

Из всех эксцентриситетов вершин графа радиус связного графа равен минимуму всех этих эксцентриситетов.

Example

На приведенном выше графике r (G) = 2, что является минимальным эксцентриситетом для 'd'.

Диаметр графа

Максимальный эксцентриситет всех вершин считается диаметром Графа G. Максимальное расстояние между вершиной и всеми остальными вершинами считается диаметром Графа G.

Notation − d(G) - Из всех эксцентриситетов вершин графа диаметр связного графа является максимальным из всех этих эксцентриситетов.

Example

На приведенном выше графике d (G) = 3; что является максимальным эксцентриситетом.

Центральная точка

Если эксцентриситет графа равен его радиусу, то он известен как центральная точка графа. Если

е (V) = r (V),

тогда «V» - это центральная точка Графа «G».

Example

В примере графика "d" - это центральная точка графика.

е (д) = г (д) = 2

Центр

Множество всех центральных точек G называется центром Графика.

Example

В примере графика {'d'} - это центр графика.

Длина окружности

В number of edges in the longest cycle of ‘G’ называется окружностью буквы G.

Example

В примере графика длина окружности равна 6, что мы получили из самого длинного цикла acfgeba или acfdeba.

Обхват

Количество ребер в кратчайшем цикле G называется его обхватом.

Notation: г (G).

Example - В примере графика Обхват графика равен 4, который мы получили из acfda, dfged или abeda самого короткого цикла.

Теорема о сумме степеней вершин

Если G = (V, E) - неориентированный граф с вершинами V = {V 1 , V 2 ,… V n }, то

n Σ i = 1 град (V i ) = 2 | E |

Corollary 1

Если G = (V, E) ориентированный граф с вершинами V = {V 1 , V 2 ,… V n }, то

n Σ i = 1 deg + (V i ) = | E | = n Σ i = 1 град - (V i )

Corollary 2

В любом неориентированном графе число вершин нечетной степени четно.

Corollary 3

В неориентированном графе, если степень каждой вершины равна k, то

k | V | = 2 | E |

Corollary 4

В неориентированном графе, если степень каждой вершины не меньше k, то

k | V | ≤ 2 | E |

| Corollary 5

В неориентированном графе, если степень каждой вершины не превосходит k, то

k | V | ≥ 2 | E |