下载文档原格式
第7章：有向图很多应用问题涉及有向图。
有向图除了有与（无向）图类似的性质之外，还有一些在图中所不具备的特殊性质。
本章除介绍有向图的基本概念外，着重介绍有向树、有向网络及其应用等问题。
§7.1有向图概述1. 基本概念定义7.1 一个有向图D 是指一个序偶><E V ，，其中V 是一个非空集合，称为D 的点集，其中的元称为D 的顶点。
E 是笛卡儿集V V ⨯的某个多重子集，称为D 的边集，其中的每一个元素均是序偶><v u ，，称为有向边，而u 称为边的始点，v 称为边的终点。
通常记>=<E V D ，，)(D V V =，)(D E E =。
从有向图的定义来看，它与上一章定义的（无向）图是相似的，最关键的区别在于有向边是有方向的，而（无向）边是无方向的。
在（无向）图中， )(v u ，和)(u v ，表示同一条边（不考虑多重边情况），但在有向图中，><v u ，和><u v ，表示的却是两个不同的边，称为对称边，虽然这两条边的端点一样。
对无向图G 的每条无向边指定一个方向，由此得到的有向图D ，称为G 的定向图。
反之，如果把一个有向图D 的每条有向边的方向去掉，由此而得到的无向图G ，称为D 的底图。
把一个有向图D 的每一条有向边反向，由此而得到的有向图称为D 的逆图，记为D ~在有向图中，两个顶点之间若有两条或两条以上的边，并且方向相同，则称为平行边，它强调了边的方向性。
有向图中的其它一些概念，像重数、圈、带圈图、无圈图、多重图、简单图、)(q p ，图、图的阶、平凡图、零图、有限图、无限图、赋权图、邻接、关联、孤立点、孤立边等等，都与（无向）图中相应概念的定义一样，这里不再重复。
在有向图中有如下的度数定义。
定义7.2 设>=<E V D ，是有向图， V v ∈，E 中以v 为起始点的有向边的个数称为v 的出度，记作)(v d +；E 忠以v 为终点的有向边的个数称为v 的入度，记作)(v d -。
第２１卷第１期 ２００７年３月
山西师范大学学报（自然科学版） Ｊｏｕｒｎａｌ ｏｆ Ｓｈａｎｘｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ Ｖ０１．２１ Ｎｏ．１
Ｍａｒ．２Ｏｏ７
文章编号：１００９－４４９０（２００７）０１－００１０－０３ ２一重自补图和有向自补图的几个性质
马杰良，王玉珏，李鑫丽 （南京信息工程大学电子与信息工程学院，江苏南京２１００４４）
摘要：本文讨论了２．重自补图和有向自补图的连通性以及２·重自补图的直径，同时以白补置换作为 工具研究了当２．重自补图或有向自补图被分成两个连通分支后，这两个连通分支之间的边数与顶点数 之间的关系． 关键词：２．重自补图；有向自补图；自补置换；度向量序列 中图分类号：０１５７．５ 文献标识码：Ａ
１相关定义和记号 本文中的有向图都是指有限、无自环且没有重弧的有向图，一般情况下用Ｄ来表示．令Ｖ（Ｄ）＝｛Ｍ。， Ｍ ，…， ｝，则序列仃＝｛（ ）（萎）．＿‘ｆ ｄ；１ｌ ｌＪ称作有向图。的度偶序列，其中ｄ ＝ｄ ，ｄ ＝ｄ ·反过来，
若仃＝｛（：：）（：：）…（Ｚ））是某个有向图的度偶序列，则称仃是可有向图实现的· 设Ｄ是一个有向图，则Ｄ的补图用Ｄ表示，这时Ｖ（Ｄ）＝Ｖ（Ｄ），并且对于Ｖ（Ｄ）中的两个顶点Ｍ和 ， ｅ＝（Ｍ， ）Ｅ Ａ（Ｄ）当且仅当ｅ＝（Ｍ， ）隹Ａ（Ｄ）．若Ｄ兰Ｄ则称Ｄ是有向自补图，并且Ｄ和Ｄ之间的同 构映射称作有向自补置换，一般用ｓ来表示．显然，若Ｄ是一个阶为Ｐ的有向自补图，则ｌ Ａ（Ｄ）ｌ＝ Ｐ（Ｐ—Ｉ）／２． 设Ａ、 是有向图Ｄ的两个顶点集，则我们用Ｄ［Ａ］、Ｄ［Ｂ］分别表示由Ａ、Ｂ导出的Ｄ的子有向图．用 Ｄ［Ａ，Ｂ］表示顶点集为Ａ Ｕ Ｂ，弧集为Ａ（Ｄ）中的一个端点在Ａ中，另一个端点在Ｂ中的弧所组成的Ｄ的 子有向图． 文中未定义的概念与记号请参阅文献［１］和［２］．
２ 相关引理
引理－［３ 设。是一个有向自补图，仃ｃ。 Ｘｄ ［
）Ｘｄ”
２／（喜））是。的度向量序列，则：
㈩ Ｐ 耋ｄ （三）；
（２）ｄ ＋ｄ ＝ｄ ＋ｄ ＝Ｐ一１，这里ｄ ＝ｄ吉（Ｍ ），ｄ ＝ｄ云（Ｍｉ），Ｍｉ Ｅ Ｖ（Ｄ）； 收稿日期：２００６·１２－２４ 基金项目：南京信息工程大学科研启动基金资助项目（ＱＤ１２）． 作者简介：马杰良（１９６４一），男，山西稷山人，南京信息工程大学电子与信息工程学院副教授，主要从事计算机软件理
论、图论及应用研究． 第１期 马杰良王玉珏李鑫丽：２－重自补图和有向自补图的几个性质 （３）用 。， ，…， 来表示 （Ｄ）的顶点，ｄ—ｉ＝（兰１，则（ ｄ２．．． ）是Ｄ的度向量序列，那么 （ ｄ—ｐ＿ｌ ｄ１）是 的度向量序列．这里我们用 表示（兰１；
（４）ｄ ＋ 。一 ＝ｄｆ＋ 。一 ＝Ｐ一１． 注：关于度向量序列的大小秩序我们有以下的规定：设订（。） ｛、ｓ，ｒｌｌＩ、 ｒ＇ｌ…（ ）），若ｒｉ＞ ，我们称
（ ）＞（ ）；若 ，ｓ ＞ ，称（ ）＞（ ）；若 ，ｓｉ ，称（ ） （ ）· 般情况下我们称７ｒ＝（ ．． ）是有向图Ｄ的度向量序列要求 ≤ ｄ２≤…≤ｄ ｐ． 引理２ 设Ｄ是一个有向自补图，那么Ｄ的基础图是２．重自补图． 这个结论的逆不成立．
３ 主要结论 定理ｌ 任一２－重自补图是连通的，任一有向自补图是弱连通的． 证明： 设Ｇ是一个有限的２－重自补图，Ｇ是不连通的，设Ｇ。、 是它的两个连通分支，以下我们将证 明Ｇ是连通的． 设 和 是 （Ｇ）中任意两点，它们在Ｇ中是不相邻的，即（ ， ）甓Ｅ（Ｇ），由２一重自补图的定义可知， 与 在Ｇ中有两条边相连，因而 、 在Ｇ中属于同一个连通分支．不妨设 、 ∈Ｖ（Ｇ。），而Ｇ是不连通的， 所以我们有ｌ ｙ（Ｇ２）ｌ＞０，即至少有一个顶点 ∈ｙ（Ｇ２），使得 与 和 都不相邻．同样由２．重自补图的 定义，在Ｇ中 与 和 都有两条边相邻，即（ ， ），（ ， ）∈Ｅ（Ｇ），这样 和 在Ｇ中是相邻的，由 、 的 任意性可知，Ｇ是连通的，而Ｇ是２－重自补的图，即Ｇ兰Ｇ，故Ｇ也是连通的，这与假设矛盾，所以Ｇ是连通 的． 由引理２知，任一有向自补图的基础图是２－重自补图，而２．重自补图是连通的，故任一有向自补图是 弱连通的． 定理２ 任一２－重自补图的直径小于或等于３． 证明： 设Ｇ是一个２．重自补图，但是Ｇ的直径ｄ（Ｇ）＞３，对于任意两点 ， ∈Ｖ（Ｇ），若 、 在Ｇ中 不相邻，那么由２－重自补图的定义可知， 、 在Ｇ中有两条边相邻，即以 、 为端点的边有两条，由于ｄ（Ｇ） ＞３，因此在Ｇ中有一点 ，它和 、 在Ｇ中都不相邻，如若不然，对于任一点），∈Ｖ（Ｇ），那么），与 、 之间 至少一点相邻，这样的话ｄ（Ｇ）≤３，这与假设相矛盾．故在Ｇ中（ ，ｕ）∈Ｅ（Ｇ），（ ， ）∈Ｅ（Ｇ），这样 ｄ（ ， ）≤２，由 、 的任意性可知ｄ（Ｇ）≤２，而Ｇ是２．重自补图，ｄ（Ｇ）＝ｄ（Ｇ），这样就与ｄ（Ｇ）＞３相 矛盾，故ｄ（Ｇ）≤３． 以上的两个定理主要讨论了２－重自补图和有向自补图在连通性和直径之间的关系．以下我们将主要 讨论当２－重自补图或有向自补图被分成两个连通分支后，这两个连通分支之间的边数与顶点数之间的关 系． 定理３ 设Ｇ是一个Ｐ阶的２－重自补图，ｓ是Ｇ上的自补置换，Ｉ／１、 ｃ （Ｇ）， ｕ ＝Ｖ（Ｇ），则有 以下的结论成立： （１）Ｉ Ｅ（Ｇ）Ｉ＝Ｐ（Ｐ—１）／２； （２）若ｓ（Ｖｉ）＝ ，则Ｇ［Ｉ／１］兰Ｇ［ ］，并且Ｉ Ｅ（Ｇ［ ， ］）Ｉ＝凡 ，这里Ｐ＝２ｎ，凡＝Ｉ Ｉ＝Ｉ Ｉ． 证明：（１）由２－重完全图的定义，Ｐ个顶点的２．重完全图的边数为Ｐ（Ｐ—１）．所以由２．重自补图的定 义可知：Ｉ Ｅ（Ｇ）Ｉ：Ｐ（Ｐ—１）． （２）由于 ｕ ＝Ｖ（Ｇ），ｓ（Ｖｉ）＝ ，ｓ∈ｓ（Ｇ），即ｓ是Ｇ的自补置换，故Ｉ Ｉ／１ Ｉ＝Ｉ Ｉ＝ｎ，ｐ＝２ｎ． 由于Ｇ［ ］＝Ｇ［ ］，故ｓ在Ｇ［Ｉ／１］之上的限制即为Ｇ［ ］与Ｇ［ ］之上的同构映射，因此， 山西师范大学学报（自然科学版） ２００７正 Ｇ［ ］兰Ｇ［ ］．而Ｉ Ｅ（Ｇ［ ］）Ｉ＋Ｉ Ｅ（Ｇ［ ］）Ｉ＝ｎ（ｎ一１），所以Ｉ Ｅ（Ｇ［ ］）Ｉ＋Ｉ Ｅ（Ｇ［ ］）Ｉ＝ｎ（ｎ １），Ｉ Ｅ（Ｇ）Ｉ＝Ｉ Ｅ（Ｇ［ ｕ ］）Ｉ＝ｎ（２ｎ一１），故Ｉ Ｅ（Ｇ［ ， ］）Ｉ＝ｎ（２ｎ一１）一ｎ（ｎ一１）＝ｎ２． 定理４ 设Ｄ是一个有向自补图，Ｉ （Ｄ）Ｉ＝２ｎ，Ｖ（Ｄ）＝｛ｕ。，ｕ ，…，ｕ ｝，仃＝（ｄ。ｄ …ｄ ）是
Ｄ的一个度向量序列，－＋ｄｉ≤－＋ｄ２≤≤ ， ：
ｆ ｄｉ。１：ｆｄ‘ １．令Ｄ。： ｕ。／／＇２…ｕ ］，Ｄ ：
、ｄ ， 、吒 ）， Ｄ［ｕ ＋ｌ ｕ ＋２…ｕ２ ］，Ｄ ＝Ｄ［Ｖｉ， ］，Ｖｉ＝｛ｔ￥Ｉｕ２…ｕ ｝， ＝｛／／％＋１ｕ ∥一１／，２ ｝，则一定有： （１）Ｉ Ａ（Ｄ。）Ｉ＋Ｉ Ａ（Ｄ２）Ｉ＝ｎ（ｎ一１）； （２）Ｉ Ａ（Ｄ ）Ｉ＝ｎ ． 证明：由于Ｄ是有向自补图，故对于任一ｕ ∈Ｖ（Ｄ），ｄ ）＋ｃｆ ）＝ｄ ＋ｄ ＝２ｎ一１．由引理１可
知，一定存在一个Ｄ的度向量序列仃＝ｄ ｄ２ ．．．ｄ 使得在Ｄ的一个自补置换之下ｓ（ ）＝ ，这样 ］兰Ｄ［ ］，同定理３完全类似的证法我们就可以得到：Ｉ Ａ（Ｄ。）Ｉ＋Ｉ Ａ（Ｄ ）Ｉ＝ｎ（ｎ一１）， Ｉ Ａ（Ｄ Ｉ＝ｎ ． 定理５ 设Ｄ是一个有向自补图， 是Ｄ的一个有向自补置换，则由 的任一圈的长度大于１的圈中 顶点导出的Ｄ的子图是有向自补图，并且由 的任两个圈的并导出的Ｄ的子图也是有向自补图． 证明：设 ＝ ｌ ２…·。 ＾，Ｉ Ｉ＞１，Ｉ Ｉ＞１， ＝（Ｍｉｌ’ｕｉ２’…，ｕｉ２ １），Ｏ＂ｉ＝（ １， ，．．．， ２）． 若令，Ｖｉ＝｛ｕｉ１’ｕ屯…．，ｕ 。｝， ＝｛ ，， …．， ｝，则 ］、Ｄ［ ］都导出有向图，并且由于 是Ｄ 的自补置换，因而 在 ］和 ］上的限制 ；和 ｆ也构成 ］和Ｄ［ ］上的自补置换，因为 和 作用于 ］与Ｄ［ ］具有 作用于它们之上相同的性质，因而 ］、Ｄ［ ］是有向自补图．同理 Ｄ［ ｕ ］也是有向自补图． 定理６ 设Ｄ是一个２ｎ阶的有向自补图， ∈ｏ（Ｄ），即 是Ｄ的一个自补置换，Ｉ Ｉ＞１，Ｉ Ｉ＞ １，Ｉ ｉ Ｉ＝２ｋｉ，Ｉ Ｉ＝２ ，令Ｖｉ＝｛ｕｉ。，ｕｉ２，…，ｕ ｝， ＝｛ ，， ，…， ｝，ｏ＂Ｉ＝｛１１，ｉ，，ｕｉ２，…，ｕ ｝， ｛ 。， ，…， ｝．定义Ｄ。＝Ｄ［ ］，Ｄ ＝Ｄ［ ］，Ｄ·， ＝Ｄ［ ｕ ］，Ｄ ·， ＝Ｄ［ ， ］，则Ｉ Ａ（Ｄ 。２）Ｉ＝４ｋ ． 证明：由定理５可知：Ｄ。、Ｄ 、Ｄ。． 都是有向自补图，又由定理３知：Ｉ Ａ（Ｄ。）Ｉ＝ｋｉ（２ｋｉ一１）， Ｉ Ａ（Ｄ２）Ｉ＝ｋ￣（２ｋｊ一１），Ｉ Ａ（Ｄ。。２）Ｉ＝（ｋ ＋尼『）（２（ｋ ＋尼，）一１）．因此由Ｄ。、Ｄ２、Ｄ。，２的关系可知：Ｉ Ａ（Ｄ 。。２）Ｉ＝Ｉ Ａ（Ｄ。。２）Ｉ—Ｉ Ａ（Ｄ。）Ｉ—Ｉ Ａ（Ｄ２）Ｉ＝（ｋｉ＋ ）（２（ｋｉ＋ ）一１）一ｋ （２ｋｉ一１）一ｋｊ（２ｋ￣一１） ４ｋ
参考文献： ［１］Ｊ．Ａ．Ｂｏｎｄｙ，Ｕ．Ｓ．Ｒ．Ｍｕｒｔｙ．Ｇｒａｐｈｔｈｅｏｒｙ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．ＴｈｅＭａｃＩＩｌｉｕａＩｌ Ｐｒｅｓｓ Ｌｉｄ．１９７６ ［２］许进．自补图理论及其应用［Ｍ］．西安：西安电子科技大学出版社，１９９９． ［３］ＲｉｎｇｅＧ．ｔｉｂｅｒ ｓｅｌｂｓｔｋｏｍｐｌｅｍｅｎｔａｒｅ ｇｒａｐｈ［Ｍ］．Ｐｕｂｌ Ｍａｔｈ Ｄｅｂｒｅｃｅｎ，１９６２．２７０—２８８． ［４］ＲｉｃｈａｒｄＡＧｉｂｂｓ．Ｓｅｌｆ－Ｃｏｍｐｌｅｍｅｎｔａｒｙ ｇｒａｐｈｓ［Ｊ］．Ｊ．Ｃｏｍｂｔｈｅｏｒｙ（Ｂ），１９７４．１６：１０６—１２３ｔ
Ｐｒｏｐｅｒｔｉｅｓ ｏｆ Ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ２－ｍｕｌｔｉｇｒａｐｈｓ ａｎｄ Ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ Ｄｉｇｒａｐｈｓ ＭＡ Ｊｉｅ－ｌｉｎｇ，ＷＡＮＧ Ｙｕ－ｊｕｅ，ＬＩ Ｘｉｎ－ｎ （￣ｏＺｌｅｇｅ Ｅｌｅｃｔｒｏｎｉｃ＆Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， ，她 ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｎａ，Ｃ，，ｇ ２１００４４，Ｊｉａｎｇｓｕ，ｃ＾ ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｅ ｐａｐｅｒ，ｔｈｅ ｃｏｎｎｅｃｔｉｖｉｔｙ ａｎｄ ｄｉａｍｅｔｅｒｓ ｏｆ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ２－ｍｕｈｉｇｒａｐｈｓ ａｎｄ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｄｉｇｒａｐｈｓ ａｒｅ ｄｉｓｃｕｓｓｅｄ。ａｎｄ ｉｆ ｔｈｅｓｅ ｇｒａｐｈｓ ｇｅｔ ｄｉｓｒｕｐｔｅｄ，ｔｈｅ ｒｅｌａｔｉｏｎｓ ｆｏｒ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｅｄｇｅｓ ａｎｄ ｖｅｒｔｉｃｅｓ ｂｅｔｗｅｅｎ ｔｈｅ ｔｗｏ ｃｏｎｎｅｃｔｅｄ ｃｏｒｎ－ ｐｏｎｅｎｔｓ ａｒｅ ａｌｓｏ ｓｔｕｄｉｅｄ ｂｙ ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｐｅｒｍｕｔａｔｉｏｎ． Ｋｅｙ ｗｏｒｄｓ：ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ２－ｍｕｈｉｇｒａｐｈｓ；ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｄｉｇｒａｐｈｓ；ｓｅｌｆ－ｃｏｍｐｌｅｍｅｎｔａｒｙ ｐｅｒｍｕｔａｔｉｏｎ；ｄｅｇｒｅｅ ｓｅ。
