Локально линейный граф
- Локально линейные графы являются графами, в которых все ребра могут быть объединены в треугольники.
- Они имеют важное значение в теории графов и используются для изучения свойств и построения других графов.
- Локально линейные графы обладают определенными свойствами, такими как четная степень в каждой вершине и регулярность.
- Существуют регулярные локально линейные графы с различными степенями и комбинациями параметров.
- Строго регулярные графики являются частным случаем локально линейных графов с определенными параметрами.
- Максимальное число ребер в локально линейном графе имеет верхнюю границу, равную
- o
- (
- n
- 2
- )
- {\displaystyle o(n^{2})}
- , но есть
- Ω
- −
- ε
- {\displaystyle \Omega (n^{2-\varepsilon })}
- для каждого
- >
- 0
- {\displaystyle \varepsilon >0}
- .
- Локально линейные графы имеют различные применения, включая составление диаграмм Гричи в квантовой логике и поиск больших гиперграфов с высоким обхватом.
Полный текст статьи: