Рёберно-транзитивный граф
В теории графов рёберно-транзитивным графом называется граф G такой, что для любых двух рёбер e1 и e2 графа G, существует автоморфизм графа G, который отображает e1 в e2[1].
Другими словами, граф рёберно-транзитивен, если его группа автоморфизма действует транзитивно на его рёбрах.
Содержание
Примеры и свойства
Рёберно-транзитивные графы включает все полные двудольные графы <math> K_{m,n}</math>, и все симметричные графы, такие как вершины и рёбра куба[1]. Симметричные графы также вершинно-транзитивны (если они связны), но в общем случае рёберно-транзитивные графы не обязательно вершинно-транзитивны. Граф Грея является примером графа, который является рёберно-транзитивным, но не вершинно-транзитивным. Все такие графы являются двудольными[1] и поэтому могут быть раскрашены всего в два цвета.
Рёберно-транзитивный граф, являющийся также регулярным, но не вершинно-транзитивным, называется полусимметричным[en]. Граф Грея снова служит примером. Рёберно-транзитивный граф должен быть двудольным и либо полусимметричным, либо бирегулярным[en][2].
Смотрите также
- Рёберная транзитивность[en] (в геометрии)
Напишите отзыв о статье "Рёберно-транзитивный граф"
Примечания
- ↑ 1 2 3 Norman Biggs. Algebraic Graph Theory. — 2nd ed.. — Cambridge, 1993. — ISBN 0-521-45897-8.
- ↑ Josef Lauri , Raffaele Scapellato Topics in Graph Automorphisms and Reconstruction. — Cambridge University Press, 2003. — С. 20—21. — ISBN 9780521529037.
Ссылки
- Weisstein, Eric W. [mathworld.wolfram.com/Edge-TransitiveGraph.html Edge-transitive graph] (англ.) на сайте Wolfram MathWorld.
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Рёберно-транзитивный граф
«Depuis nos grands succes d'Austerlitz vous savez, mon cher Prince, писал Билибин, que je ne quitte plus les quartiers generaux. Decidement j'ai pris le gout de la guerre, et bien m'en a pris. Ce que j'ai vu ces trois mois, est incroyable.«Je commence ab ovo. L'ennemi du genre humain , comme vous savez, s'attaque aux Prussiens. Les Prussiens sont nos fideles allies, qui ne nous ont trompes que trois fois depuis trois ans. Nous prenons fait et cause pour eux. Mais il se trouve que l'ennemi du genre humain ne fait nulle attention a nos beaux discours, et avec sa maniere impolie et sauvage se jette sur les Prussiens sans leur donner le temps de finir la parade commencee, en deux tours de main les rosse a plate couture et va s'installer au palais de Potsdam.
«J'ai le plus vif desir, ecrit le Roi de Prusse a Bonaparte, que V. M. soit accueillie еt traitee dans mon palais d'une maniere, qui lui soit agreable et c'est avec еmpres sement, que j'ai pris a cet effet toutes les mesures que les circonstances me permettaient. Puisse je avoir reussi! Les generaux Prussiens se piquent de politesse envers les Francais et mettent bas les armes aux premieres sommations.
«Le chef de la garienison de Glogau avec dix mille hommes, demande au Roi de Prusse, ce qu'il doit faire s'il est somme de se rendre?… Tout cela est positif.
«Bref, esperant en imposer seulement par notre attitude militaire, il se trouve que nous voila en guerre pour tout de bon, et ce qui plus est, en guerre sur nos frontieres avec et pour le Roi de Prusse . Tout est au grand complet, il ne nous manque qu'une petite chose, c'est le general en chef. Comme il s'est trouve que les succes d'Austerlitz aurant pu etre plus decisifs si le general en chef eut ete moins jeune, on fait la revue des octogenaires et entre Prosorofsky et Kamensky, on donne la preference au derienier. Le general nous arrive en kibik a la maniere Souvoroff, et est accueilli avec des acclamations de joie et de triomphe.
«Le 4 arrive le premier courrier de Petersbourg. On apporte les malles dans le cabinet du Marieechal, qui aime a faire tout par lui meme. On m'appelle pour aider a faire le triage des lettres et prendre celles qui nous sont destinees. Le Marieechal nous regarde faire et attend les paquets qui lui sont adresses. Nous cherchons – il n'y en a point. Le Marieechal devient impatient, se met lui meme a la besogne et trouve des lettres de l'Empereur pour le comte T., pour le prince V. et autres. Alors le voila qui se met dans une de ses coleres bleues. Il jette feu et flamme contre tout le monde, s'empare des lettres, les decachete et lit celles de l'Empereur adressees a d'autres. А, так со мною поступают! Мне доверия нет! А, за мной следить велено, хорошо же; подите вон! Et il ecrit le fameux ordre du jour au general Benigsen
