Graph isomorphism and theorems of Birkhoff type
Graph isomorphism and theorems of Birkhoff type
复制标题
图同构与Birkhoff型定理
作者：
G. Tinhofer
具有邻接矩阵A和B的两个图G和G ′称为ds-同构当且仅当存在满足XA =BX的双随机矩阵X.第二节给出了关于ds-同构的一个完整的不变量集。在A =B（ds-自同构）的情形下，主要问题是：对于哪些图G，G的ds-自同构的多面体等于G的自同构的凸船体？在第3节中，对G是树或G是圈的情形给出了肯定的回答。相应的定理类似于Birkhoff关于双随机矩阵的著名定理，当一个双随机矩阵X =BX时，Ds-Isomorphie是一个经典同构关系的证明.在Abschnitt 2中，将有一个不变系统被定义为同构。Für den FallA=B（ds-自同构）lautet die Hauptfrage：Für welche GraphenG is das Polytop derds-自同构gleich der klassischen Automorphismen？在Abschnitt 3 wird diese Frage für Kreise und Bärheumpositiv beantwortet.该定理与伯克霍夫的随机矩阵相似。
Two graphsG andG′ having adjacency matricesA andB are called ds-isomorphic iff there is a doubly stochastic matrixX satisfyingXA=BX.Ds-isomorphism is a relaxation of the classical isomorphism relation. In section 2 a complete set of invariants with respect tods-isomorphism is given. In the case whereA=B (ds-automorphism) the main question is: For which graphsG the polytope ofds-automorphisms ofG equals the convex hull of the automorphisms ofG? In section 3 a positive answer to this question is given for the cases whereG is a tree or whereG is a cycle. The corresponding theorems are analoga to the well known theorem of Birkhoff on doubly stochastic matrices.ZusammenfassungZwei GraphenG undG′ werdends-isomorph genannt, wenn eine doppelt stochastische MatrixX existiert mitXA=BX, wobeiA undB die Adjazenzmatrizen vonG undG′ sind.Ds-Isomorphie ist eine Vergröberung der klassischen Isomorphierelation. In Abschnitt 2 wird ein vollständiges Invariantensystem bezüglichds-Isomorphie vorgestellt. Für den FallA=B (ds-Automorphismus) lautet die Hauptfrage: Für welche GraphenG ist das Polytop derds-Automorphismen gleich der konvexen Hülle der klassischen Automorphismen? In Abschnitt 3 wird diese Frage für Kreise und Bäume positiv beantwortet. Die entsprechenden Theoreme sind Analoga zu dem bekannten Satz von Birkhoff über doppelt stochastische Matrizen.