Представление скалярного произведения графика
Представление скалярного произведения простого графа — это метод представления графа с использованием векторных пространств и скалярного произведения из линейной алгебры . Каждый график имеет представление скалярного произведения. [1] [2] [3]
Определение
[ редактировать ]Пусть G — граф с множеством вершин V . Пусть F — , поле а f — функция от V до F. к такой, что xy является ребром G тогда и только тогда, когда f ( x ) · f ( y ) ≥ t . Это скалярное G. произведение Число t называется порогом скалярного произведения , а наименьшее возможное значение k называется размерностью скалярного произведения. [1]
Характеристики
[ редактировать ]- Пороговый график — это график скалярного произведения с положительным t и размерностью скалярного произведения 1. [1]
- Каждый интервальный график имеет размерность скалярного произведения не более 2. [1]
- Каждый планарный граф имеет размерность скалярного произведения не более 4. [4]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б с д Фидучча, Чарльз М.; Шайнерман, Эдвард Р .; Тренк, Энн ; Зито, Дженнифер С. (1998), «Скалярное произведение графиков», Discrete Mathematics , 181 (1–3): 113–138, doi : 10.1016/S0012-365X(97)00049-6 , MR 1600755 .
- ^ Райтерман, Дж.; Рёдль, В.; Шиняйова, Э. (1989), «Вложения графов в евклидовы пространства», Дискретная и вычислительная геометрия , 4 (4): 349–364, doi : 10.1007/BF02187736 , MR 0996768 .
- ^ Райтерман, Дж.; Рёдль, В.; Шиняйова, Э. (1992), «О вложении графов в евклидовы пространства малой размерности», Журнал комбинаторной теории , серия B, 56 (1): 1–8, doi : 10.1016/0095-8956(92)90002- Ф , МР 1182453 .
- ^ Канг, Росс Дж.; Ловас, Ласло ; Мюллер, Тобиас; Шайнерман, Эдвард Р. (2011), «Представление скалярного произведения плоских графов», Электронный журнал комбинаторики , 18 (1): Статья 216, MR 2853073 .
Внешние ссылки
[ редактировать ]
СМИ, связанные с матричным представлением графов, на Викискладе?
