PDF《离散数学图论作业 4 - 欧拉图》

离散数学图论作业

4 - 欧拉图 Problem

1 试确定下方所示各图是否具有欧拉回路.

若存在欧拉回路,则构造出一条欧拉回路.若不存在,试确定这个图 是否具有欧拉通路.若存在欧拉通路,则构造出一条欧拉通路. Problem

2 对哪些 m 和n值来说,完全二部图 Km,n 具有 1) 欧拉回路? 2) 欧拉通路? Problem

3 请画出所有互不同构的具有

5 个顶点的欧拉图(仅考虑无向简单图) . Problem

4 证明或反驳:若无向简单图 G1 和G2 是顶点数、边数均相等的欧拉图,则G1 和G2 同构.

1 Problem

5 若无向简单图 G 是欧拉图,证明或反驳: 1) 当G的顶点数是奇数时,若补图 ? G 是连通的,则?G中存在欧拉通路. 2) 当G的顶点数是偶数时,若补图 ? G 是连通的,则?G中存在欧拉通路. Problem

6 给定无向简单图 G(|G| ≥ 3) ,定义线图 L(G) 如下: ? 对G中的每条边,L(G) 中恰好有一个顶点与之对应;

? L(G) 中任意两点相邻当且仅当它们在 G 中对应的两条边相邻(即有一个公共顶点) . 证明若 G 是简单、连通的 r-正则图,则L(G) 是欧拉图.然后举例说明反之不一定成立. 2