Графы имеют различные свойства, которые используются для характеристики графов в зависимости от их структуры. Эти свойства определены в конкретных терминах, относящихся к области теории графов. В этой главе мы обсудим несколько основных свойств, которые являются общими для всех графиков.
Расстояние между двумя вершинами
Это число ребер в кратчайшем пути между вершиной U и вершиной V. Если существует несколько путей, соединяющих две вершины, то кратчайший путь рассматривается как расстояние между двумя вершинами.
Обозначение — d (U, V)
Может быть любое количество путей из одной вершины в другую. Среди них вам нужно выбрать только самый короткий.
пример
Посмотрите на следующий график —
Здесь расстояние от вершины ‘d’ до вершины ‘e’ или просто ‘de’ равно 1, поскольку между ними есть одно ребро. Существует много путей от вершины ‘d’ до вершины ‘e’ —
- да, а, бе
- дф, фг, гэ
- де (считается для расстояния между вершинами)
- дф, фц, ca, ab, be
- да, ac, cf, fg, ge
Эксцентриситет вершины
Максимальное расстояние между вершиной и всеми остальными вершинами рассматривается как эксцентриситет вершины.
Обозначение — e (V)
Расстояние от конкретной вершины до всех других вершин графа берется, и среди этих расстояний эксцентриситет является наибольшим из расстояний.
пример
На приведенном выше графике эксцентриситет «а» равен 3.
Расстояние от «a» до «b» равно 1 («ab»),
от ‘a’ до ‘c’ равно 1 (‘ac’),
от «а» до «d» равно 1 («объявление»),
от ‘a’ до ‘e’ равно 2 (‘ab’ — ‘be’) или (‘ad’ — ‘de’),
от ‘a’ до ‘f’ равно 2 (‘ac’ — ‘cf’) или (‘ad’ — ‘df’),
от ‘a’ до ‘g’ равно 3 (‘ac’ — ‘cf’ — ‘fg’) или (‘ad’ — ‘df’ — ‘fg’).
Таким образом, эксцентриситет равен 3, что является максимумом от вершины «а» от расстояния между «ag», которое является максимальным.
Другими словами,
е (б) = 3
е (с) = 3
е (д) = 2
е (е) = 3
е (е) = 3
е (г) = 3
Радиус связного графа
Минимальный эксцентриситет от всех вершин рассматривается как радиус графа G. Минимальный среди всех максимальных расстояний между вершиной до всех остальных вершин рассматривается как радиус графа G.
Обозначение — r (G)
Из всех эксцентриситетов вершин графа радиус связного графа является минимумом всех этих эксцентриситетов.
Пример — На приведенном выше графике r (G) = 2, что является минимальным эксцентриситетом для «d».
Диаметр графика
Максимальный эксцентриситет от всех вершин рассматривается как диаметр графа G. Максимальный из всех расстояний между вершиной до всех других вершин рассматривается как диаметр графа G.
Обозначение — d (G)
Из всех эксцентриситетов вершин графа диаметр связного графа является максимальным из всех этих эксцентриситетов.
Пример. На приведенном выше графике d (G) = 3; что является максимальным эксцентриситетом.
Центральная точка
Если эксцентриситет графа равен его радиусу, то он называется центральной точкой графа. Если
e (V) = r (V),
тогда «V» является центральной точкой графа «G».
Пример — в примере графика ‘d’ является центральной точкой графика.
e (d) = r (d) = 2
Центр
Множество всех центральных точек «G» называется центром графа.
Пример. В примере графика {‘d’} является центром графика.
Длина окружности
Число ребер в самом длинном цикле «G» называется окружностью «G».
Пример. На графике примера длина окружности равна 6, что мы получили из самого длинного цикла acfgeba или acfdeba.
обхват
Число ребер в кратчайшем цикле G называется его обхват.
Обозначения — g (G).
Пример — в примере графика обхват графа равен 4, который мы получили из кратчайшего цикла acfda или dfged или abeda.
Теорема о сумме степеней вершин
Если G = (V, E) ненаправленный граф с вершинами V = {V 1 , V 2 ,… V n }, то
Следствие 1
Если G = (V, E) ориентированный граф с вершинами V = {V 1 , V 2 ,… V n }, то
Следствие 2
В любом неориентированном графе число вершин с нечетной степенью является четным.
Следствие 3
В неориентированном графе, если степень каждой вершины равна k, то
к | V | = 2 | E |
Следствие 4
В неориентированном графе, если степень каждой вершины не меньше k, то
к | V | ≤ 2 | E |
Следствие 5
В неориентированном графе, если степень каждой вершины не более k, то
к | V | ≥ 2 | E |