У математиці два-граф це (невпорядкована) множина трійок, вибраних зі скінченної множини вершин X таким чином, що будь-яка (невпорядкована) четвірка з містить парне число вибраних трійок два-графа. У регулярному (однорідному) два-графі будь-яка пара вершин лежить у тому самому числі трійок два-графа. Два-графи вивчають через їх зв'язок з рівнокутними прямими, зв'язок регулярних два-графів із сильно регулярними графами, а також через зв'язок регулярних два-графів зі скінченними групами, оскільки багато із цих графів мають цікаві групи автоморфізмів.
Два-графи не є графами, і їх не слід плутати з іншими об'єктами, які називаються 2-графами в теорії графів, зокрема, з 2-регулярними графами. Для їх розрізнення використовують слово «два», а не цифру «2», с. 58—59..
Два-графи увів Хіґман як природні об'єкти, що виникають під час роботи з деякими простими групами. Відтоді їх інтенсивно вивчали Зайдель, Тейлор та інші, розглядаючи множини рівнокутних прямих, сильно регулярних графів та інших об'єктів.
Приклади На множині вершин {1, …, 6} такий невпорядкований набір трійок є два-графом:
123 124 135 146 156 236 245 256 345 346
Цей два-граф є регулярним, оскільки будь-яка пара різних вершин присутня разом рівно в двох трійках.
Якщо дано звичайний граф , то набір трійок вершин з , у яких породжений підграф має непарне число ребер, утворює два-граф на . Будь-який два-граф можна подати в такому вигляді, с. 876, примечание 13.2.. Цей приклад показує стандартний спосіб побудови два-графа зі звичайного графа.
Наведемо складніший приклад. Нехай — дерево зі множиною ребер . Множина всіх трійок ребер, що не лежать на одному шляху в утворюють два-граф на множині , як процитовано в , с. 876, підсумок 13.12..
Перемикання та графи
Два-граф еквівалентний класу перемикання графів, а також (знаковому) класу перемикання .
Перемикання множини вершин у (звичайному) графі означає змінення суміжності кожної пари вершин, одна з яких у множині, а інша не у множині — суміжна пара стає несуміжною, а несуміжна пара стає суміжною. Ребра, кінцеві вершини яких належать множині, або обидва кінці не алежать множині, не змінюються. Графи є еквівалентними за перемиканням, якщо один можна отримати з іншого перемиканням. Клас еквівалентності за перемиканням називають класом перемикання. Перемикання ввели Ван Лінт і Зайдель і розвинув Зайдель. Назву перемикання графів або перемикання Зайделя введено, зокрема, щоб відрізнити від перемикання .
У наведеній вище стандартній побудові два-графів зі звичайного графа два графи дають той самий два-граф тоді й лише тоді, коли вони еквівалентні за перемиканням, тобто належать до одного класу перемикання.
Нехай — два-граф на множині . Для будь-якого елемента із визначимо граф із множиною вершин , у якому вершини і суміжні тоді й лише тоді, коли належить . У цьому графі буде ізольованою вершиною. Ця побудова оборотна: візьмемо звичайний граф , додамо новий елемент до множини вершин , зберігши набір ребер, і скористаємося розглянутою стандартною побудовою. Цей два-граф мовою блок-схем називають розширенням графа вершиною .
Графу відповідає знаковий повний граф на тій самій множині вершин, ребра якого від'ємні, якщо належать , і додатні, якщо не належать . І навпаки, є підграфом і складається з усіх вершин та від'ємних ребер. Два-граф можна визначити як множину трійок вершин, які утворюють від'ємний трикутник (трикутник із непарним числом від'ємних ребер) у . Два знакових повних графи дають той самий два-граф тоді й лише тоді, коли вони еквівалентні за перемиканням.
Перемикання і пов'язані: перемикання тих самих вершин дає граф і відповідний йому знаковий повний граф.
Матриця суміжності Матриця суміжності два-графа це знакового повного графа. Тобто вона симетрична, має нулі на діагоналі, і значення поза діагоналлю дорівнюють ±1. Якщо — граф, який відповідає знаковому повному графу Σ, то цю матрицю називають (0, − 1, 1) матрицею суміжності або графа . Матриця суміжності Зайделя має нулі на головній діагоналі -1 для елементів, відповідних суміжним вершин, і +1 для елементів, відповідних несуміжним вершинам.
Якщо графи і перебувають у одному класі перемикання, мультимножини власних значень двох матриць суміжності Зайделя для і збігаються, оскільки матриці подібні, с. 61..
Два-граф на множині є регулярним тоді й лише тоді, коли його матриця суміжності має лише два різних власних значення, скажімо , де , с. 878, #13.24..
Рівнокутні прямі Будь-який два-граф еквівалентний множині прямих у деякому багатовимірному евклідовому просторі, кут між будь-якою парою прямих з якої однаковий. Множину прямих можна побудувати з два-графа з вершинами в такий спосіб. Нехай — найменше власне значення два-графа, і припустимо, що його кратність дорівнює . Тоді матриця є додатно напіввизначеною матрицею рангу , і її можна подати як матрицю Грама скалярних добутків векторів у евклідовому просторі розмірності . Ці вектори також мають однакову норму (а саме, ) та попарний скалярний добуток , а кут між будь-якою парою з прямих, на яких лежать ці вектори, дорівнює , де . Навпаки, будь-яка множина неортогональних прямих у евклідовому просторі, кут між будь-якою парою яких однаковий, дає два-граф.
У позначеннях, наведених вище, найбільша потужність задовольняє нерівності , і межа досягається тоді й лише тоді, коли два граф регулярний.
Сильно регулярні графи Два-графи на , що складаються з усіх можливих трійок з , і порожні (що не мають трійок) є регулярними два-графами, але їх прийнято вважати тривіальними два-графами і, як правило, виключають із розгляду.
Нетривіальний два-граф на множині є регулярним тоді й лише тоді, коли для будь-якого із граф є сильно регулярним з (степінь будь-якої вершини вдвічі більший за кількість вершин, суміжних обом з будь-якої несуміжної пари вершин). Якщо ця умова виконується для одного із , вона виконується для всіх елементів із , с. 62, теорема 4.11..
Звідси випливає, що нетривіальний регулярний два-граф має парну кількість вершин.
Якщо — регулярний граф, розширений два-граф якого має вершин, то є регулярним два-графом тоді й лише тоді, коли є сильно регулярним графом із власними значеннями , і для яких виконується або , с. 62, теорема 4.12..
Примітки
Література