Реберний граф
З Вікіпедії, безкоштовно encyclopedia
В теорії графів реберним графом L(G) неорієнтованого графа G називається граф L(G), що представляє сусідство ребер графа G.
Поняття реберного графа для цього графа настільки звісно, що незалежно було введено багатьма авторами. Звичайно, кожний з них давав свою назву: Оре[1] назвав цей граф «графом, що суміжний», Сабідуссі[2] — «графом похідної», Байнеке [3] — «похідним графом», Сешу і Рід[4] — «реберно-вершинно-двоїстим», Кастелейн[5] — «графом, що покриває», Менон[6] — «приєднаним» («пов'язаним»)[7][8][9].
Одна з найперших та найважливіших теорем про реберні графи належить Вітні, який довів, що за одним винятком, структура графа G повністю визначається реберним графом. Іншими словами, за одним винятком, весь граф може бути відновлений з реберного графа.