文档介绍：§
Linear Programming
运筹学课件
①
②
③
④
⑤
⑥
①
②
③
④
⑤
⑥
⑦
①
②
③
④
⑤
⑥
⑦
设G有p个连通分支,则G的邻接矩阵可以表示成分块矩阵
寻找G的连通分支:从任一点i出发,寻找与i连通的所有点,构成集合N1,则G[N1]是G的一个连通分支。再在剩下的点中类似地寻找其它连通分支。
①
②
③
④
⑤
⑥
①
②
③
④
⑤
⑥
⑦
①
②
③
④
⑤
⑥
⑦
设G有p个强连通分支,则G的邻接矩阵可以表示成分块矩阵
寻找G的强连通分支:从任一点i出发,寻找与i强连通的所有点,构成集合N1,则G[N1]是G的一个强连通分支。再在剩下的点中类似地寻找其它强连通分支。
图G的割边:如果从G中删去它就使图的连通分支数严格增加的边
①
②
③
④
⑤
⑥
⑦
G的一条边是割边当且仅当这条边不包含在G的任何回路中。
①
②
③
④
⑤
①
②
③
④
⑤
①
②
③
④
⑤
①
②
③
④
⑤
①
②
③
④
⑤
①
②
③
④
⑤
反证法
①
②
③
④
⑤
①
②
③
④
⑤
①
②
③
④
⑤
①
②
③
④
⑤
①
②
③
④
⑤
①
②
③
④
⑤