大家好，欢迎来到IT知识分享网。
握手定理(Handshaking Theorem)：握手数之和为偶数,两倍的边数（度数之和为两倍的边数，对于有向图就是出度与入度的和）
但是，满足握手定理，握手图不一定存在，比如握手序列（4，4，1，1，1，1）
例子：一个三角形
δ ( G ) ≤ 2 , ∃ 环 路 长 度 至 少 为 δ ( G ) + 1 δ(G)\leq 2,\exists 环路长度至少为δ(G)+1 δ(G)≤2,∃环路长度至少为δ(G)+1
证明：
最长路证法
V 0 → V 1 → V 2 → V 3 … … → V k V_0 \rightarrow V_1 \rightarrow V_2\rightarrow V_3……\rightarrow V_k V0→V1→V2→V3……→Vk
则 与 V 0 相 邻 的 顶 点 一 定 在 最 长 路 中 ( 否 则 最 长 路 能 够 增 广 ) 则与V_0相邻的顶点一定在最长路中(否则最长路能够增广) 则与V0相邻的顶点一定在最长路中(否则最长路能够增广)
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/119982.html
