Теория графов - основные свойства
Графы имеют различные свойства, которые используются для описания графов в зависимости от их структур. Эти свойства определены в конкретных терминах, относящихся к области теории графов. В этой главе мы обсудим несколько основных свойств, общих для всех графов.
Расстояние между двумя вершинами
Это количество ребер на кратчайшем пути между вершиной 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 }, то
Corollary 1
Если G = (V, E) ориентированный граф с вершинами V = {V 1 , V 2 ,… V n }, то
Corollary 2
В любом неориентированном графе число вершин нечетной степени четно.
Corollary 3
В неориентированном графе, если степень каждой вершины равна k, то
Corollary 4
В неориентированном графе, если степень каждой вершины не меньше k, то
| Corollary 5
В неориентированном графе, если степень каждой вершины не превосходит k, то