首页 > 代码库 > 图论-课堂例题

图论-课堂例题

证明:在连通图G中,任二个最长路必有公共顶点。

(反证法)

(1)

o------o-------o-------o  p

o------o-------o-------o  q

(2)

o  o------o-------o

    |

    |

o      o------o-------o

矛盾

2、在连通图中,d(v)=偶数,w(G-v) <= d(v)/2

 

例1.8 设一金库只有一个大门,其内部被分隔成一些小房间(把走廊、门厅

等都看成房间)。各房间除了一个放有稀世大钻石的房间外,都有偶数个门(大门也

是一个门)。则能撬开每个门的大盗一定可将钻石偷走。

证明 不计金库大门(则大门门厅也只有奇数个门),以金库的所有房间为顶

点集作一图G ,两顶点间用一边相连当且仅当对应的两个房间有一个门相连。则图

G 中恰只有与大门门厅及存放钻石的房间对应的两个顶点(设为x 与y )为奇点,

其余顶点都是偶点。

我们的问题变成要证明任一图G 中若恰只有两个奇点x 与y ,则G 中一定存

在(x ,y )路。

设若不然,则G 不连通,且x 与y 在G 的不同分支中。于是,G 中包含x 的分

支,是一个只包含一个奇点的图,这与推论132 相矛盾。//

图论-课堂例题