Перейти к навигации Перейти к поиску
Представление скалярного произведения простого графа - это метод представления графа с использованием векторных пространств и скалярного произведения из линейной алгебры . Каждый граф имеет представление скалярного произведения. [1] [2] [3]
Определение [ править ]
Пусть G граф с множеством вершин V . Пусть F - поле, а f - функция из V в F k такая, что xy является ребром G тогда и только тогда, когда f ( x ) · f ( y ) ≥ t . Это представление скалярного произведения G . Число t называется порогом скалярного произведения , а наименьшее возможное значение k называется размерностью скалярного произведения. [1]
Свойства [ править ]
- Пороговый граф является скалярное произведение граф с положительной точки т и размерности продукта 1. [1]
- Каждый интервальный график имеет размерность скалярного произведения не более 2. [1]
- Каждый планарный граф имеет размерность скалярного произведения не более 4. [4]
См. Также [ править ]
Ссылки [ править ]
- ^ a b c d Fiduccia, Charles M .; Шайнерман, Эдвард Р .; Тренк, Энн ; Сито, Дженнифер С. (1998), "Представление скалярного произведения графов", дискретная математика , 181 (1-3): 113-138, DOI : 10.1016 / S0012-365X (97) 00049-6 , МР 1600755.
- ^ Reiterman, J .; Rödl, V .; Šiňajová, Е. (1989), " О вложении графов в евклидовых пространств", Дискретная & Вычислительная геометрия , 4 (4): 349-364, DOI : 10.1007 / BF02187736 , МР 0996768 .
- ^ Reiterman, J .; Rödl, V .; Šiajová, E. (1992), "О вложении графов в евклидовы пространства малой размерности", Журнал комбинаторной теории , серия B, 56 (1): 1–8, doi : 10.1016 / 0095-8956 (92) 90002- F , MR 1182453 .
- ^ Канг, Росс Дж .; Ловас, Ласло ; Мюллер, Тобиас; Шайнерман, Эдвард Р. (2011), «Точечные произведения плоских графов», Electronic Journal of Combinatorics , 18 (1): Paper 216, MR 2853073 .
Внешние ссылки [ править ]
- СМИ, связанные с матричным представлением графиков на Викискладе?