当前位置：文档之家 › 圈图和2p阶完全二部图的齐次分解

圈图和2p阶完全二部图的齐次分解

  • 格式：pdf
  • 大小：148.29 KB
  • 文档页数：3

Ｖ０ ． ＮＯ ２ Ｉ ２１ ．
Ｊ ｎ ２ １ ｕ ．０２
圈 图 和
阶 完 全 。 图 的 齐 次 分 解 －
覃 树 仁
（ 州华 商职 业 学 院 公 共 基 础 课 程 教 学 部 ， 东 广 州 ５ １ ０ ） 广 广 Ｉ３０
摘要 ： 循环群和 ２ 在 ｐ阶 群 的 自同构 群 的基 础 上 ， 到 了圈 图和 ２ （ 得 ｐ ｐ是 素数 ） 完全 二 部 图的 所 有 齐 次 分 解 的 阶
具体 构 造．
关键 词 ： 图 ； 全 二 部 图 ； 次分 解 ； 圈 完 齐 同构 分 解 ； 自同构 群 中 图 分 类 号 ： １７ ５ Ｏ ５ ． 文献标识码 ： Ａ 文 章 编 号 ：０ ７— ８ ４ ２ １ ） ２— ０ ９— ２ １０ ０ ３ （ ０ ２ ０ ０ ２ ０
齐次 分解 的同 构分解 ， 以用 置换 群进 中对任 意 的 点传 递 图做 了初 步研 究 ．
齐次 分解 如今 已成为 代数 图论 的热 门研究 课题 ． 文针 对 圈图 Ｃ 本 和 ２ （ ｐ Ｐ是素 数 ） 阶完全 二部 图
分解 进行研 究 ， 得到 了这 两类 图的所 有齐 次分 解 的具体 构造 ．主要结 果是 定理 １和定 理 ２ ．
的因子 是Ｃ 和 Ｃ．
收 稿 日期 ： ０ ２—０ ２１ ３—０ ５
， 集 为 ｕ的 图称为 由 导 出 的子 图 ， 边
作 者 简 介 ： 树 仁 （９ Ｏ ） 男 ， 西 桂 平 人 ， 州华 商 职 业 学 院 公 共 基 础 课 程 教 学 部 教 师 覃 １ ８一 ， 广 广
本文 中 厂 表示 一个 图 ，
，厂， ，，ｕ（ 分别 表示 厂 的顶 点集 ， Ａ Ｅ Ａ ｔ ，） 弧集 ， 集 和 全 自同构 群 ， 他 符 号 边 其
和术语 参见 文献 ［ ］ ［ ］ １ 和 ２ ．图的 同构分解 是 把 图分 解 为一些 同构 的子 图的并 ． 般 的 同构 分解 无 法建 立 系 一 统 的理论进 行研 究． 名 图论专 家 Ｌ 著 Ｉ Ｈ和 Ｐ Ａ Ｇ Ｒ Ｃ Ｅ在 文 献 ［ ］ ｃ Ｒ Ｅ Ｅ ３ 中介 绍 了点 传 递对 称 图 的一 种 称 为
我们把 的元素 尸 以及 Ｐ 的导 出子 图 （ ， 称 为 齐次 分 解 （ ， ， ） 因子 ， 时也 称 为 的 因 Ｐ） Ｇ 厂， 的 有
子．定义 说 明 是 弧集 Ｐ 的生成 子 图 厂 自同构 群且 在 的
上 的作 用是 传递 的 ， Ｇ能够把 的任何 一个 因
河 南教 育 学 院 学报 （ 自然 科 学 版 ）
（） ２ 如果 ｎ ｒ ４ 为 偶 数 ，那 么 圈 图 ｃ （＞ ） ｔ １ 有且 只有 两 个 齐 次 分 解 ： ＝（ ， ｕ（ ， 。 和 Ｆ Ｆ Ｍ Ａ ｔ ｃ ） ｃ ， ） ＝
的齐 次 上 传递 ，
定义 １ 设 ＝｛ 一， （ ≥２ 是 图 厂 的弧集 Ａ 的一个 划分 ， ＜Ｇ ｕ（ 且 Ｍ 在 Ｐ Ｐ ｝ｋ ） ， Ｍ ≤Ａ ｔＦ） 称 （ ， 厂， ） 图 厂 的指 数 为 ｋ的齐 次分 解 ， Ｇ， 是 如果
（ ） 保持 的每个 元素 Ｐ 不动 ， １Ｍ 且 （ ） 是 Ｇ的不 变划 分且 Ｇ在 上 的导 出作 用 Ｇ 在 上 传递． ２ 、
因子 厂 的度数都是 １ 厂 同构 于顺 时针 方向的有 向圈ｃ 或完美 匹配÷ Ｋ ， 且当 ｎ是奇数时只能是 且 并
二
－－－
厂 Ｃ ． 兰
证 明 设 （ ， ，， ） Ｇ， 是度数 为 素数 Ｐ的连通 图 厂 的指数 为 ｋ的齐次分 解 ， 由引理 １得 ＝ ｐ并 且 厂 的 度 数都 是 １ 又 因 在 ，
Ｍ 在
上 传递 ， ， 是 正则 图． Ｇ在 上 的作 用传 递 ， 以 Ｇ传 递 地 置换 的 全体 元 素 ， 而对 任何 两 故 因 所 从
个 因子 ， 和 厂 都 有 ｏ（ ）＝ ａ（ ）＝ｒｖ ｌ，）＝ ｋ 证毕 ． Ｚ厂 ｖｌＦ ，ａ（ ｒ．
引理 ２ 如果 ｎ ｎ ） （ ≥３ 阶连 通 图 厂 的度数 为 素数 Ｐ （ Ｇ ，， ） ， Ｍ， ，１ 是指 数 为 ｋ的齐 次分解 ， 么 的每个 那
子置 换成 另外 一个 因子 ， 各个 因子彼 此 同构． 因此 ， 齐次 分解 是保持 子 图 的点 传递 性质 的一 种 同构 分解 ．
引理 １ 设 （ Ｇ， ） 图 厂 的指数 为 ｋ的齐次 分解 ， ｋ整 除 ， 的度数 ｖｌＦ） Ｍ， 厂， 是 则 ａ（ ． 证明 设 （ Ｇ， ） 图 厂 的指数 为 ｋ的齐次 分解 ， Ｍ， Ｆ， 是 厂 是 的一个 因子 ， 由定 义 １知 ， ≤Ａ ｔ ， ） ｕ（ 且
二
＝
上传 递 ， 以当 为偶 数时 ， 能同构 于顺 时针 方 向的有 向圈 ｃ 或完 美 匹 所 ，只
配÷ ； ｎ 当 是奇数时只能是 厂 兰ｃ ．
定 义 ２ 设 厂 是一 个 图 ， ｕ是 Ｅ 的一个 非 空子集 ． ， 顶 集 为 记 为 ｒ［ Ｕｉ ． 定理 １ （） 果 ｎ ｎ ） １如 （ ≥３ 为奇数 ， 么圈 图 Ｃ 有 唯一 的齐 次分解 Ｆ ＝（ ，ｕ（ ， ） 其 中 那 Ｍ Ａ ｔ Ｃ ） Ｃ ， ，
第 ２ 卷 第 ２期 １
２１ ０ ２年 ６ 月
河 南教 育 学 院 学报 （自然 科 学 版 ）
Ｊｕ ｎ ｌ ｆＨｅ ａ ｎ ｔｕｅｏ ｕ ａｉｎ（ ｔｒｌＳ ｉｎ ｅＥｄｔ ｎ） ｏ ｒａ ｎ ｎ Ｉｓｉ ｔ ｆＥｄ ｃ ｔ ｏ ｔ ｏ Ｎａｕａ ｃｅ ｃ ｉ ｏ ｉ

合集下载

离散数学第8,9章课后习题答案

离散数学第8,9章课后习题答案

第8章 习题参考答案1. 在一次10周年同学聚会上，想统计所有人握手的次数之和，应该如何建立该问题的图论模型？解：将每个同学分别作为一个节点，如果两个人握过一次手就在相应的两个节点之间画一条无向边，于是得到一个无向图。

一个人握手的次数就是这个节点与其他节点所连接的边的条数，进而可得出所有人握手的次数之和。

2. 在一个地方有3户人家，并且有3口井供他们使用。

由于土质和气候的关系，有些井中的水常常干枯，因此各户人家要到有水的井去打水。

不久，这3户人家成了冤家，于是决定各自修一条路通往水井，打算使得他们在去水井的路上不会相遇。

试建立解决此问题的图论模型。

解：将3户人家分别看做3个节点且将3口井分别看做另外3个节点，若1户人家与1口井之间有一条路，则在该户人家与该口井对应的节点之间连一条无向边，这样就得到一个无向图。

3. 某人挑一担菜并带一条狼和一只羊要从河的一岸到对岸去。

由于船太小，只能带狼、菜、羊中的一种过河。

由于明显的原因，当人不在场时，狼要吃羊，羊要吃菜。

通过建立图论模型给出问题答案。

解：不妨认为从北岸到南岸，则在北岸可能出现的状态为24=16种，其中安全状态有下面10种：（人，狼，羊，菜），（人，狼，羊），（人，狼，菜），（人，羊，菜），（Φ），（人，羊），（菜），（羊），（狼），（狼，菜）；不安全的状态有下面6种：（人）（人，菜）（人，狼）（狼，羊，菜）（狼，羊）（羊，菜）。

线将北岸的10种安全状态看做10个节点，而渡河的过程则是状态之间的转移，这样就得到一个无向图，如图8-1所示。

图8-1从上述无向图可以得出安全的渡河方案有两种：第1种：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（狼）→（人，狼，羊）→（羊）→（人，羊）→（Φ）。

(人，狼，羊，菜)(人，狼，羊)(人，狼，菜)(人，羊，菜)(人，羊) (狼，菜) (羊) (狼) (菜) (Φ)第2中：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（菜）→（人，羊，菜）→（羊）→（人，羊）→（Φ）。

图论之图的分类

图论之图的分类

图论之图的分类简单图不含圈和重边的图称为简单图。

圈是⼀条边，它的两个顶点相同。

重边是同⼀对端点具有的多条边。

⼀个简单图的补图也是简单图。

团是图中两两相邻的定点的集合。

独⽴集（稳定集）是图中两两互不相邻的顶点组成的集合。

定理⼀：在任何⼀个图中，所有顶点的度数和是边数的2倍。

推论：每⼀个图的奇顶点个数是偶数个。

不规则图（irregular graph）如果图G的每两个顶点都有不同的度数，那么这样⼀个⼆阶或⼆阶以上的图G称为不规则图。

不存在不规则图⼏乎不规则图（almost irregular graph）如果图G只含有⼀对具有相同度数的顶点，那么这样的⼀个⼆阶或者⼆阶以上的图称为⼏乎不规则图。

补图（complement）对于每⼀个整数n(n>=2)都恰好存在阶为n的两个⼏乎不规则图，且他们互为补图。

对于⼀个给定的正整数集，其中最⼤数为n，存在⼀个n+1阶的图使得其顶点的度数恰好等于这些整数。

⼆部图⼆部图的顶点集由两个独⽴的顶点集组成，独⽴顶点集中的任意两个顶点之间不含有边。

⽐如任务分配图。

正则图（regular graph）如果图G的每个顶点都有相同的度数，则称图G为正则图。

如果度数是r，那么图G就称为r-正则图（r-regular graph）。

定理：对于任意两个整数r和n，且都不为奇数，0<=r<=n-1，那么⼀定会存在n阶的r-正则图。

例如：5阶图，不存在1-正则图和3-正则图，因为⼀个图顶点度为奇数的顶点数是偶数个。

不规则多重图与加权图 对任意⼀个阶数n>=3的图G，其⾄多有⼀个孤⽴点并且没有两个相邻的端点，那么存在⼀个不规则加权图的底图为G。

令其边从集合{1,2,3,...,k}中取值，⽣成⼀个不规则加权图，这样的最⼩数的数k叫做G的不规则强度（irregular strength），记作s（G）。

⼦图（subgraph）真⼦图、⽣成⼦图（spanning subgraph）：顶点集为图G的顶点集。

《电路基础》第8讲 齐次定理、叠加定理、替代定理

《电路基础》第8讲 齐次定理、叠加定理、替代定理


I1(2) )
( R2
R3
R4 )( I2(1)
I
(2 2
)
)
US
R4 IS
+
R4IS
─
R4
6
(R1+ R2) I1
+ R2 I2 =US
R2 I1 +(R2 + R3 + R4) I2 = US R4 IS
(2.5 - 4)
(R1 R2 )( I1(1) I1(2) )
R2 (I2(1) I2(2) ) US
第8讲 齐次定理、叠加定理和替代定理
1、齐次定理（homogeneity property)
齐次定理描述了线性电路的齐次性或比例性。 其内容为： 对于具有唯一解的线性电路，当只有一个激励源 F（独立 电压源或独立电流源）作用时，其响应Y（电路任一处的电压或 电流）与激励F成正比。即
如果 Us
R Uo
(2) 叠加定理仅适用于线性电路（包括线性时变电路）， 而不适用于非线性电路。
(3) 叠加定理只适用于计算电流和电压，而不能用于计算 功率， 因为功率不是电流或电压的一次函数。证明如下：
i i' i'' u u' u''
p ui (u' u'' )(i' i'' ) u'i' u''i''
+ +
+ -1A
以-1A电流源置换N2，得：12
u2
0.5i
u
u2 6(i 1) 12 12V
-
1A
5Ω
-
19
2-齐次二部距离正则图的特征值的性质

2-齐次二部距离正则图的特征值的性质

第 33 卷 第 2 期 2018 年 06 月
邢台学院学报 JOURNAL%OF%XINGTAI%UNIVERSITY
Vol.%33,%No.2 Jun.%2018
2－齐次二部距离正则图的特征值的性质
国慧
（邢台学院数信学院， 河北邢台 054001）
摘 要： 在对距离正则图的研究中， 距离正则图的代数性质是一个重要的内容， 国内外的专家学者对此进行了广泛
齐次二部距离正则图的交叉阵列只有四种情况，
下面只考虑交叉阵列为 ，k，k-1，k-2，…2，1；1，2…，k-1，k ，，k≥3 的情况。
引理 6： 设 祝=（X，R） 为直径 d≥3， 价 k≥3
的二部距离正则图， 兹0>兹1>…>兹d 为 祝 的互不相同 的特征值， 则以下条件等价：
（1）祝 为 2-齐次的，且 兹1=k-2；
定义： 设 祝=（X，R） 为直径 d≥3 的距离正则 图，价 k≥3。称为 2-齐次的，当对所有的整数 （ i 1≤ i≤d-1）及所有 的 点 x，y，z，坠（x，y）=2，坠（x，z）=1，坠 （y，z）=i，数值
γi = ，w∈X/α(x，w)=1，α(y，w)=1，α(z，w)=i-1 ， 的大小与 x，y，z 的选取无关， 只依赖于 i 的选取[1]。
图， 记 E=Er， 则对所有的整数 （ i 0≤i≤d）及所有 的点 x，y∈X，坠（x，y=i）， 以下成立：
-
ρi-1(Exy
-
-Eyx
)+ρi
0
(Exy
0
-Eyx
)+ρi+1
+
(Exy
+
-Eyx
)=兹t
ρi