图论基础与网络流习题集锦

图论习题课⼀、填空题1、对下列图，试填下表（是??类图的打〝√ 〞，否则打〝?〞）。

①②③2、若图G=中具有⼀条汉密尔顿回路，则对于结点集V 的每个⾮空⼦集S ，在 G 中删除S 中的所有结点得到的连通分⽀数为W ，则S 中结点数|S|与W 满⾜的关系式为。

3、设有向图D 为欧拉图，则图D 中每个结点的⼊度．4、数组{1，2，3，4，4}是⼀个能构成⽆向简单图的度数序列，此命题的真值是 .5、“3,3K 是欧拉图也是哈密顿图”这句话是_______。

(填对或错)6、极⼤可平⾯图的每⼀个⾯的次数都是_________．7、5阶完全图的边连通度是．8、图G是2-⾊的当且仅当G是．⼆、选择题1、下列⽆向图可能不是偶图的是( )(A) ⾮平凡的树(B)⽆奇圈的⾮平凡图(C) n(1)n ⽅体图(D) 平⾯图2、关于平⾯图，下列说法错误的是( )(A) 简单连通平⾯图中⾄少有⼀个度数不超过5的顶点；(B)极⼤外平⾯图的内部⾯是三⾓形，外部⾯也是三⾓形；(C) 存在⼀种⽅法，总可以把平⾯图的任意⼀个内部⾯转化为外部⾯；(D) 平⾯图的对偶图也是平⾯图。

3、已知图G的邻接矩阵为，则G有（）．A．5点，8边B．6点，7边C．6点，8边D．5点，7边4、设图G＝，则下列结论成⽴的是( )．A．deg(V)=2∣E∣B．deg(V)=∣E∣C．EvVv2)deg(=∑∈D．Vv=∑∈)deg(5、设完全图K n有n个结点(n≥2)，m条边，当（）时，K n中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数6、设G是连通平⾯图，有v个结点，e条边，r个⾯，则r= ( )．A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋27、下列定义正确的是( )．A含平⾏边或环的图称为多重B不含平⾏边或环的图称为简单图C含平⾏边和环的图称为多重D不含平⾏边和环的图称为简单图8、以下结论正确是( )．A仅有⼀个孤⽴结点构成的图是零图B⽆向完全图Kn每个结点的度数是nC有n(n>1)个孤⽴结点构成的图是平凡图D图中的基本回路都是简单回路9、下列数组能构成简单图的是( )．(A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3)10、n阶⽆向完全图Kn中的边数为（）．(A) 2)1(+nn(B) 2)1(-nn(C) n (D)n(n+1)11、以下命题正确的是( )．(A) n(n≥1)阶完全图Kn都是欧拉图(B) n(n≥1)阶完全图Kn都是哈密顿图(C) 连通且满⾜m=n－1的图(∣V∣=n,∣E∣=m)是树(D) n(n≥5)阶完全图Kn都是平⾯图12、下列结论不正确是( )．(A) ⽆向连通图G是欧拉图的充分必要条件是G不含奇数度结点(B) ⽆向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点(C) 有向连通图D是欧拉图的充分必要条件是D的每个结点的⼊度等于出度(D) 有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的⼊度等于出度13、⽆向完全图K4是（）．（A）欧拉图（B）哈密顿图（C）树（D）平⾯图14、在如下各图中（）欧拉图。

【HDU】1213 How Many Tables 基础并查集★1272 小希的迷宫基础并查集★(简单题)1325&&poj1308 Is It A Tree? 基础并查集★1856 More is better 基础并查集★1102 Constructing Roads 基础最小生成树★1232 畅通工程基础并查集★+1233 还是畅通工程基础最小生成树★1863 畅通工程基础最小生成树★1875 畅通工程再续基础最小生成树★1879 继续畅通工程基础最小生成树★3371 Connect the Cities 简单最小生成树★1301 Jungle Roads 基础最小生成树★1162 Eddy's picture 基础最小生成树★1198 Farm Irrigation 基础最小生成树★1598 find the most comfortable road 枚举+最小生成树★★1811 Rank of Tetris 并查集+拓扑排序★★3926 Hand in Hand 同构图★3938 Portal 离线+并查集★★2489 Minimal Ratio Tree dfs枚举组合情况+最小生成树★4081 Qin Shi Huang's National Road System 最小生成树+DFS★★4126 Genghis Khan the Conqueror 枚举+最小生成树+DFS(难)★★★★1829&&poj2492 A Bug's Life 基础种类并查集★1558 Segment set 计算几何+并查集★3461 Code Lock 并查集(有点难想到)★★3367 Pseudoforest最大生成树★2473 Junk-Mail Filter 并查集+设立虚父节点(马甲)★★3172 Virtual Friends 带权并查集★3635 Dragon Balls 带权并查集★3047 Zjnu Stadium 带权并查集★3038 How Many Answers Are Wrong 种类并查集★★2818 Building Block 带权并查集★3234 Exclusive-OR 异或并查集(难)★★★2121 Ice_cream’s world II 最小树形图(要输出根有点恶心)★★4009 Transfer water 最小树形图(模板题)★3311 Dig The Wells 斯坦纳树(状压DP)(模板题)★★4085 Peach Blossom Spring 斯坦纳树(状压DP)(有可能是森林...)★★★2586 How far away ？ LCA★2874 Connections between cities LCA★3486 Interviewe RMQ★2888 Check Corners 二维RMQ★3183 A Magic Lamp RMQ(有点难想到,有点难联系到RMQ)★★【POJ】1258 最经典的MST★1789 Truck History 最小生成树★1287 Networking 简单★2349 Arctic Network 简单★1611 The Suspects 并查集★2377 kruskal★2524 Ubiquitous Religions 并查集★2236 Wireless Network 并查集+计算几何★2560 Kruskal并查集★1861 Kruskal★3625 prim★1679 - The Unique MST(基础) 判断MST是否唯一★3522 - Slim Span(基础) 求一颗生成树，让最大边最小边差值最小★2485 Highways MST中的最长边★2395 最小生成树的最长边★1751 Highways 求出方案★POJ-1182 食物链种类并查集★★POJ 1456 Supermarket 贪心+区间合并★POJ-1703 种类并查集★POJ-1988 种类并查集★POJ-1733 Parity game 种类并查集，先要离散化一下，不影响结果★POJ-1417 True Liars(难) 并查集+DP 种类并查集★★POJ-2912 Rochambeau(难) baidu的题,很不错...是食物链的加强版.判断裁判比较难想.★★★POJ 2728 Desert King(中等) 最优比率生成树★★POJ 1639 Picnic Planning(较难) 顶点度数有限制的最小生成树★★POJ 3164 Command Network(难) 最小树形图★★poj3723 好题!!! ★★poj3228 好好题!!! ★★【ZOJ】ZOJ-3261 逆向并查集★★====================以下是最短路系列========================= 【HDU】1548 A strange lift 基础最短路(或bfs)★1690bus system –松弛小麻烦2544 最短路基础最短路★3790 最短路径问题基础最短路★2066 一个人的旅行基础最短路(多源多汇,可以建立超级源点和终点)★2112 HDU Today 基础最短路★1874 畅通工程续基础最短路★1217 Arbitrage 货币交换 Floyd (或者 Bellman-Ford 判环)★1245 Saving James Bond 计算几何+最短路★1317 XYZZY Bellman-Ford判环,有负权★1535 Invitation Cards 有向图的来回最短路,(反向建图)★1546 Idiomatic Phrases Game 最短路★2680 Choose the best route 最短路★2923 Einbahnstrasse最短路★3339 In Action 最短路+背包★2224 The shortest path 双调旅行商问题★★2807 The Shortest Path 矩阵运算+最短路(floyd)★★1595 find the longest of the shortest枚举+最短路(删掉任意一条边的最长最短路)★★3986 Harry Potter and the Final Battle 枚举+最短路(删掉任意一条边的最长最短路)★★1599 find the mincost route floyd求最小环★1839 Delay Constrained... 二分下限+最短路(带限制最短路)★★3631 Shortest Path Floyd插点法★★4114 Disney's FastPass最短路+二维状压DP(难)★★★3832 Earth Hour 三点连通(斯坦纳树)★3873 Invade the Mars Dij变体(好题!,带限制最短路)★★★4063 Aircraft 几何构图+最短路★★★★hdu4179 Difficult Routes dis[][]开二维状态的最短路(带限制最短路)★★1869 六度分离 Floyd最短路★1385 Minimum Transport Cost 最短路+输出路径(输出字典序最小路径,有点恶心)★★1224 free DIY Tour 最短路+输出路径★1142 A Walk Through the Forest 最短路+记忆搜索★★1596 find the safest road 乘积最小的最短路★1598 find the most comfortable road 二分速度差+最短路(带限制最短路)★★2722 Here We Go(relians) Again 最短路★2962 Trucking 二分+最短路(带限制最短路)★★1690 Bus System 最短路★2433 Travel 删边+最短路之和(预处理桥边)★★★2363 Cycling 二分+最短路(带限制最短路)★★2377 Bus Pass 最短路(寻找一个点的最长最短路最小)★★2833 WuKong最短路+记忆化搜索(求两条最短路的最多公共点)★★1688 Sightseeing 最短次短路条数★★3191 How Many Paths Are There 次短路条数★★2482 Transit search 最短路★★★3768 Shopping 最短路+dfs(或最短路+状压DP)★★3035 War 平面图最小割(建图麻烦)★★3870 Catch the Theves平面图最小割(建图麻烦)★★3860 Circuit Board 平面图最小割(建图麻烦)★★【POJ】1062 昂贵的聘礼竟然可以和最短路联系起来★★1094 Sorting It All Out Floyd判环+拓扑排序★1125 Stockbroker Grapevine Floyd★1135 Domino Effect 最短路,比较有意思★★1161 Walls 最短路(图太恶心了)★★1502 MPI Maelstrom Floyd★1511 Invitation Cards 来回最短路★1556 The Doors 计算几何+最短路★★1724 ROADS 带限制的最短路,dis[][]开二维来记录信息(或广搜)★★1734 Sightseeing trip floyd最小环路径★1797 Heavy Transportation 二分枚举+最短路★1847 Tram 简单最短路★1860 Currency Exchange 货币兑换★1949 Chores 反向建边,求最长路★★2139 Six Degrees of Cowvin Bacon Floyd★2240 Arbitrage 货币兑换★2253 Frogger二分+最短路★2312 坦克大战spfa最短路本质变形-->广搜★2387 Til the Cows Come Home 基础最短路★2394 Checking an Alibi 最短路★2449 Remmarguts' Date A*求第K短路★★2457 Part Acquisition 最短路 (输出路径)★★2472 106 miles to Chicago 乘积最短路(log一下,乘变加)★★2502 Subway2570 Fiber Network floyd3013 圣诞树3037 Skiing3072 Robot3114 Countries in War 强联通+最短路3160 Father Christmas flymouse强联通+最长路3255 Roadblock3259 Wormholes （寻找负权回路）3268 Silver Cow Part3311 Hie with the Pie floyd+状压3328 Cliff Climbing3439 Server Relocation3463 Sightseeing 次短路条数31593521 Geometric Map 计算几何+最短路3549 GSM phone 计算几何+最短路3594 Escort of Dr. Who How3613 Cow Relays 经过N条边的最短路 // floyd + 二分矩阵3615 Cow Hurdles3621 最优比率环3635 full tank?3660 传递闭包3662 Telephone Lines======================以下是差分约束系列======================= 【HDU】1384 Intervals1529 Cashier Employment1531 King1534 Schedule Problem3440 House Man3592 World Exhibition3666 THE MATRIX PROBLEM【POJ】120112751364171629492983315931693687============================以下是二分匹配系列================== 普通匹配,多重匹配【HDU】1068 Girls and Boys最大独立集1150 Machine Schedule最小点覆盖1151 Air Raid最小边覆盖1179 Ollivanders: Makers of Fine Wands since 382 BC.最大匹配裸1281 棋盘游戏最大匹配1498 50 years, 50 colors最小点覆盖1507 Uncle Tom's Inherited Land*最大匹配1528 Card Game Cheater最大匹配1845 Jimmy’s Assignment最大2063 过山车最大匹配2119 Matrix最小点覆盖裸2444 The Accomodation of Students最大匹配2768 Cat vs. Dog最大独立集3081 Marriage Match II—最大流+二分3360 National Treasures最小点覆盖1045 也可搜索1350 最小路径覆盖-----还有待理解3118 类似二分匹配3729最大匹配2389最大匹配—HK算法1054最小点-小小的麻烦—最大匹配/2-双向边2819 完全匹配1668 二分+多重匹配3605 多重匹配3861 强连通+二分匹配2236 无题IIhdu3468hdu4185 oil—建图麻烦【POJ】1087 A Plug for UNIX1274 The Perfect Stall1469 COURSES1486 Sorting Slides 二分图的必须边1548 Robots1698 Alice's Chance1719 Shooting Contest1904 King's Quest 求二分图所有可能的匹配边2060 Taxi Cab Scheme 最小路径覆盖2112 Optimal Milking 二分+多重匹配2226 Muddy Fields 行列的覆盖2239 Selecting Courses2289 Jamie's Contact Groups 二分+多重匹配2446 Chessboard2536 Gopher II2584 T-Shirt Gumbo2594 Treasure Exploration 可相交最小路径覆盖2672 Hotkeys2724 Purifying Machine3020 Antenna Placement3041 Asteroids 简单行列匹配3189 Steady Cow Assignment 二分+多重匹配3207 Ikki's Story IV - Panda's Trick3216 Repairing Company3343 Against Mammoths3692 Kindergarten2771 最大独立集===========================以下是KM算法系列================== 【HDU】2255 奔小康赚大钱1533 Going Home1853 Cyclic Tour3488 Tour3435 A new Graph Game2426 Interesting Housing Problem2853 Assignment3718 Similarity3722 Card Game3395 Special Fish2282 Chocolate2813 One fihgt one(水题)2448 Mining Station on the Sea3315 My Brute3523 Image copy detection【POJ】2195 Going Home 最小权值匹配2400 Supervisor, Supervisee 输出所有最小权匹配2516 Minimum Cost 最小权值匹配或最小费用流3565 Ants3686 The Windy's最小权值匹配===================以下是最大团&稳定婚姻系列==================== 【HDU】1530 Maximum Clique1435 Stable Match3585 maximum shortest distance 二分+最大团1522 Marriage is Stable1914 The Stable Marriage Problem【POJ】1129 四色定理着色问题1419 最大独立集2989 极大团3487 The Stable Marriage Problem 稳定婚姻===================以下是强双联通系列======================== 【HDU】强连通:1269 迷宫城堡判断是否是一个强连通2767 Proving Equivalences 至少加几条边让整个图变成强连通-缩点后入度出度3836 Equivalent Sets 至少加几条边让整个图变成强连通1827 Summer Holiday 传递的最小费用3072 Intelligence System 传递的最小费用3861 The King’s Problem 强连通+二分匹配3639 Hawk-and-Chicken 强连通缩点 + 树形dp（累加子节点的总权值）3594 Cactus 仙人掌图双连通:2242 考研路茫茫——空调教室双联通缩点+树形DP2460 Network 边双连通3849 By Recognizing These Guys, We Find Social Networks Useful 双连通求桥3896 Greatest TC 双连通4005 The war 边双连通LCA:2586 How far away ？2874 Connections between cities3078 Network LCA+排序3830 Checkers 二分+LCA【POJ】强连通:1236 Network of Schools2553 The Bottom of a Graph 好题！找出度为0的集合2186 Popular Cows 好题！缩点后找出度为0的，其他分量都指向它的集合2375 Cow Ski Area 强连通2762 Going from u to v or from v to u? 缩点+拓扑排序3160 Father Christmas flymouse强连通+最短路3180 The Cow Prom 判断有几个环，分量中元素大于1的个数3114 Countries in War 强连通+最短路3592 Instantaneous Transference 强连通分量+最长路1904 King's Quest 强连通+并查集双连通：1523SPF 求割点与割点对应连通分量3694 Network 边双连通 (同hdu2460)3177 Redundant Paths 构造边双连通缩点—重边不要加入3352 Road Construction构造边双连通缩点—同3177无重边2942 Knights of the Round Table (点双连通经典题)1515 Street Directions (无向图改有向图)1438 One-way Traffic (混合图改有向图)LCA:1330 Nearest Common Ancestors1470 Closest Common Ancestors1986 Distance Queries3417 Network3728 The merchant LCA+并查集,更新询问2763 Housewife Wind LCA+树状数组=====================以下是2-SAT系列==================== 【HDU】3062 Party1824 Let's go home3622 Bomb Game3715 Go Deeper1815 Building roads2723 Get Luffy Out1816 Get Luffy Out *1814 Peaceful Commission4115 Eliminate the Conflict【POJ】2296 Map Labeler2723 Get Luffy Out2749 Building roads3207 Ikki's Story IV - Panda's Trick3648 Wedding3678 Katu Puzzle3683 Priest John's Busiest Day3905 Perfect Election======================以下是欧拉回路系列======================= 【HDU】1878 欧拉回路判断裸3018 Ant Trip 一笔画问题11162894 兹鼓欧拉回路1956混合欧拉3472 混合欧拉【POJ】2513 欧拉路1041 John's trip 欧拉回路1386 Play on Words 单词接龙2230 Watchcow欧拉回路2513 Colored Sticks 无向图欧拉路2337 Catenyms欧拉路径1392 Ouroboros Snake 兹鼓欧拉回路1780 code1637 混合欧拉【zoj】1992======================以下是拓扑排序系列======================== 【HDU】1285 确定比赛名次2094 产生冠军2647 Reward工人要求奖励-反向建图3342 Legal or Not1811 Rank of Tetris 拓扑+并查集3231 三维拓扑【POJ】1094 Sorting It All Out Floyd+拓扑2367 Genealogical tree3660 Cow Contest3687 Labeling Balls 神奇的拓扑1128 Frame Stacking DFS版拓扑1270 Following Orders 拓扑+回溯1420 Spreadsheet 模拟拓扑2762 Going from u to v or from v to u? 强连通+拓扑3553 Task schedule========================以下是竞赛图系列======================== 竞赛图下的哈密顿问题Strange Country II ZOJ-3332Task Sequences POJ-1776The book SGU-122Tour Route POJ-3780Tour Route HDOJ-3414=========================以下是网络流系列======================= 1532 Drainage Ditches(基础) [最大流]3549 Flow Problem(基础) [最大流]3572 Task Schedule [最大流]任务分配,判断满流2732 Leapin' Lizards( 难) [最大流]3338 Kakuro Extension [最大流][数和]神奇最大流行进列出2883 kebab [最大流]判断满流3605 Escape [最大流](多重匹配3081 Marriage Match II [二分最大流]+并查集3277 Marriage Match III [二分最大流]同上,多了拆点3416 Marriage Match IV [最大流]最短路+最大流2485 Destroying the bus stations [最大流]最短路+最大流3468 Treasure Hunting [最大流](二分匹配)+最短路3551 Hard Problem [最大流]3998 Sequence(难) [DP+最大流]最长上升子序列3917 Road constructions [最大权闭包]3879 Base Station [最大权闭包]3061 Battle [最大权闭包]3996 Gold Mine [最大权闭包]3472 HS BDC [混合欧拉]hdu4183 来回走不重复点的网络流.-------------------------1533 Going Home(基础) [费用流]3488 Tour [费用流]圈3435 A new Graph Game [费用流]圈1853 Cyclic Tour [费用流]圈2686 Matrix [费用流]3376 Matrix Again [费用流]3667 Transportation [费用流]拆边3315 My Brute [费用流](可用KM)3395 Special Fish [费用流](可用KM匹配)2448 Mining Station on the Sea [费用流](可用最短路+KM匹配) 4067 Random Maze(难) [费用流]3947 River Problem(难) [费用流]神奇费用流,流量不等式建图3046 Pleasant sheep and big big wolf [最小割]1565 方格取数(1) [最小割]1569 方格取数(2) [最小割]3820 Golden Eggs [最小割]方格加强3491 Thieves [最小割]最小点割集3657 Game [最小割]最大点权独立集3313 Key Vertex [最小割]3251 Being a Hero [最小割]3157 Crazy Circuits [上下流]3002 King of Destruction [全局最小割]3691 Nubulsa Expo [全局最小割]【POJ】1087 A Plug for UNIX [最大流](可用二分匹配)1274 The Perfect Stall [最大流](可用二分匹配)1325 Machine Schedule [最大流](可用二分匹配)1698 Alice's Chance [最大流](可用二分匹配)2239 Selecting Courses [最大流](可用二分匹配)2446 Chessboard [最大流](可用二分匹配) 好题啊2536 Gopher II [最大流](可用二分匹配)2771 Guardian of Decency [最大流]二分匹配最大独立集3041 Asteroids [最大流](简单二分匹配)2584 T-Shirt Gumbo [最大流](多重匹配)3189 Steady Cow Assignment(中等) [二分最大流](多重匹配) 1149 PIGS [最大流] 绝对经典的构图题1273 Drainage Ditches [最大流](基础)1459 Power Network(基础) [最大流]3281 Dining [最大流]2112 Optimal Milking(基础) [二分最大流]2289 Jamie's Contact Groups [二分最大流]2391 Ombrophobic Bovines(中等) [二分最大流]2455 Secret Milking Machine(基础) [二分最大流]3228 Gold Transportation [二分最大流](并查集)2699 The Maximum Number of Strong Kings(较难) [枚举人数 + 最大流]3498 March of the Penguins(中等) [最大流]枚举汇点,满足点容量限制的网络流2987 Firing(较难) [最大权闭包]1637 Sightseeing tour(Crazy) [混合欧拉]2135 Farm Tour [费用流] (来回最短路)2175 Evacuation Plan(中等) [费用流] 消圈2195 Going Home [费用流]2516 Minimum Cost [费用流]3422 Kaka's Matrix Travels(中等) [费用流]拆点3680 Intervals(较难) [费用流]经典,费用流+离散化3686 The Windy's [费用流](KM匹配)3762 The Bonus Salary! [费用流]1815 Friendship(中等) [最小割]最小点割集1966 Cable TV Network(中等) [最小割]最小点割集2125 Destroying The Graph(难) [最小割]最小点权覆盖3084 Panic Room(中等，好题) [最小割]边连通度3204 Ikki's Story I - Road Reconstruction(基础) [最小割]求关键边3308 Paratroopers(较难) [最小割]乘积取对数,最小点权覆盖3436 ACM Computer Factory [最小割]收集流,残留搜集找边3469 Dual Core CPU(中等) [最小割]收集流3921 Destroying the bus stations [最小割]点连通2396 Budget(中等) [有源汇的上下界可行流]3155 Hard Life(很挑战一题) [最大密度子图]2914 Minimum Cut [无向图最小割]====================以下是dancing links系列====================== 1001 Easy Finding POJ-37401002 Power Stations HDOJ-36631003 Treasure Map ZOJ-32091004 Lamp HDOJ-28281005 whosyourdaddy HDOJ-34981006 Bomberman - Just Search! HDOJ-3529 1007 Square Destroyer POJ-10841008 Matrix HDOJ-21191009 Divisibility HDOJ-33351010 Radar HDOJ-22951011 Fire station HDOJ-36561012 Repair Depots HDOJ-31561013 Dominoes HDOJ-25181014 Street Fighter HDOJ-39571015 Sudoku Killer HDOJ-14261016 Sudoku POJ-26761017 Sudoku POJ-30741018 Sudoku POJ-30761019 Su-Su-Sudoku HDOJ-27801020 Sudoku HDOJ-31111021 Sudoku HDOJ-39091022 Squiggly Sudoku HDOJ-40691023 Triangle War II ZOJ-30381024 A Puzzling Problem HDOJ-16031025 Maximum Clique HDOJ-1530hust1017 精确覆盖。

图论复习题（二）图论复习题一、选择题1．设图G ＝<V , E >，v ∈V ，则下列结论成立的是 ( C ) ． A ．deg(v )=2∣E ∣ B ． deg(v )=∣E ∣ C ．E v Vv 2)deg(=∑∈ [PPT 23] D ．Ev Vv =∑∈)deg(定理1 图G=（V ，E ）中，所有点的次之和为边数的两倍 2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110则G 的边数为( B )．A ．6B ．5C ．4D ．33、 设完全图K n 有n 个结点(n ≥2)，m 条边，当（ C ）时，K n 中存在欧拉回路．A ．m 为奇数B ．n 为偶数C ．n 为奇数D ．m 为偶数解释：K n 每个结点的度都为n －1，所以若存在欧拉回路则n －1必为偶数。

n 必为奇数。

4．欧拉回路是（ B ）A. 路径B. 简单回路[PPT 40]C. 既是基本回路也是简单回路D.既非基本回路也非简单回路5．哈密尔顿回路是（ C ）A. 路径B. 简单回路C. 既是基本回路也是简单回路D.既非基本回路也非简单回路[PPT 40]：哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可以是简单回路的边不重复。

6．设G 是简单有向图，可达矩阵P(G)刻划下列关系中的是（ C ） A 、点与边 B 、边与点 C 、点与点 D 、边与边7．下列哪一种图不一定是树（C ）。

A.无简单回路的连通图B. 有n 个顶点n-1条边的连通图C. 每对顶点间都有通路的图D. 连通但删去一条边便不连通的图8．在有n 个结点的连通图中，其边数（B ）A.最多有n-1条B.至少有n-1条C.最多有n 条D.至少有n 条9．下列图为树的是（C ）。

A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a GB 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a GC 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a GD 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 10、下面的图7-22是（C ）。

图论与网络流理论课后答案图论与网络流理论是计算机科学中非常重要的两门课程。

学生在学习这些课程时，需要掌握各种算法和理论，以便在实际应用中解决各种问题。

然而，在学习课程后，学生需要进行一些练习，以巩固他们所学的内容，并提高他们的技能水平。

一种非常有效的学习方法是通过解答题目来练习。

本文将提供一些图论与网络流理论的练习题答案，帮助学生评估他们自己的能力，发现自己的错误，以及加强自己的学习。

1. 图论（1）给定一个无向图G=(V,E)，其中V为点的集合，E为边的集合。

一个环是一条从一个点出发，经过若干不同的点，最终返回起点的路径。

请问，如何判断一个无向图中是否存在环？答：可以使用深度优先搜索（DFS）算法来判断是否存在环。

在遍历图的过程中，如果遇到一个已经标记为已访问的顶点，且该顶点不是当前顶点的父亲，则该图中存在一个环。

（2）给定一个带权重的图G=(V,E)，其中每条边都有一个权重。

请问，如何找到一个最小生成树？答：可以使用Prim算法或Kruskal算法来找到一个最小生成树。

在Prim算法中，从一个起始节点开始，将其与最短的相邻节点相连，并将其加入到生成树中。

然后，重复此过程，直到所有节点都加入到生成树中。

在Kruskal算法中，首先将所有边按权重排序，然后按照升序逐个添加边，并检查是否形成了环。

如果没有形成环，则将该边添加到生成树中，否则舍弃该边。

2. 网络流理论（1）给定一个网络流G=(V,E)，其中源点为s，汇点为t，每条边都有一个容量和一个费用。

请问，如何找到一个最小费用流？答：可以使用最小费用最大流算法来找到一个最小费用流。

该算法包含两个步骤。

第一步是找到一个最大流，可以使用Ford-Fulkerson 算法或者Edmonds-Karp算法。

第二步是通过增广路径来增加流量，直到达到最小费用。

（2）给定一个有向无环图G=(V,E)，其中每个节点都有一个点权，且每条边都有一个边权。

请问，如何找到从源点s到汇点t的一条最长路径？答：可以使用动态规划来解决该问题。

OI刷题录——图论前言省选过后写了一些图论题，从中选出50道集合在这里，给想写图论的一点帮助。

大部分较为基础，神犇就不要过来虐我了。

大部分题目是POJ的，每道题后都给出我提交情况，写明WA，TLE，RE等的原因，方便大家吸取教训。

50道题目包括：最短路3道，Tarjan 4道，最小生成树3道，差分约束系统6道，网络流29道（包含线性规划与网络流24题），杂项5道。

提供我的每道题AC代码以及其他资料的压缩包，以下为下载地址：百度云网盘115网盘最短路spfa，dijkstra为图论基础算法，应熟练应用。

spfa是可以扩展到二维的。

先将距离小于等于R的点对连无向边，形成一张图。

dist[i][j]表示从j到达i时的最短路，朝向为向量(xi-xj，yi-yj)。

spfa时枚举跟i相连的点k，由状态dist[i][j]转移到状态dist[k][i]，更新完dist[k][i]的值后将其入队(如果还未入队的话)。

spfa结束后取Min{dist[n][i]}，1≤i＜n。

本题关键在于计算向量转角，题目中已经提示使用atan2( )。

atan2(x，y)：返回向量(x，y)跟x轴正方向的夹角(弧度制)，值域为(-π，π]，(x，y)在x轴上方返回值为正，下方为负。

两向量夹角：D=abs(atan2(x1，y1)-atan2(x2，y2))，如果D>π，则D=2π-D，最后应转成角度制即D=D/π*180。

Compile Error：POJ下sqrt和atan2应进行强制类型转换。

Wrong Answer：最开始没有用atan2，用了比较矬的方法。

滑槽顶、楼梯底和终点为传送入口，滑槽底、楼梯顶和起点为传送出口。

一旦达到入口就会被送到出口。

从每个出口向其后面的每个入口连一条有向边，贪心计算步数作为权值，然后跑一遍spfa即可得出答案。

步数计算：1、一开始将步长定为最大，以这步长前进。

2、如果会踩到中途某一传送入口则减小步长，如果还是入口则再减小，减小到不是入口用最大步跨过去，继续以最大步前进，又遇到入口则重复操作。

图论及网络总复习题一、选择题1、设G是由5个顶点构成的完全图，则从G中删去（）边可以得到树。

A．6 B．5 C．8 D．42、下面哪几种图不一定是树（）。

A．无回路的连通图B．有n个结点，n-1条边的连通图C．对每对结点间都有通路的图D．连通但删去任意一条边则不连通的图。

3、5阶无向完全图的边数为（）。

A．5 B．10 C．15 D．204、把平面分成x个区域，每两个区域都相邻，问x最大为（）A．6 B．4 C．5 D．35、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（）A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 6、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的（）。

A．充分条件B．必要条件C．充分必要条件D．既不充分也不必要条件7、设G=<V，E>为有向图，V={a,b,c,d,e,f}，E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是（）。

A．强连通图B．单向连通图C．弱连通图D．不连通图8、无向图G中的边e是G的割边（桥）的充分必要条件是（）。

A．e是重边B．e不是重边C．e不包含在G的任一简单回路中D．e不包含在G的某一简单回路中9、在有n个结点的连通图中，其边数（）A．最多有n-1条B．至少有n-1条C．最多有n条D．至少有n条10．设无向简单图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n211．n个结点的完全有向图含有边的数目（）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）12．在一个无向图中，所有顶点的度数之和等于所有边数（）倍。

A．1/2 B．2 C．1 D．413．连通图G是一棵树，当且仅当G中（）A．有些边不是割边B．所有边都是割边C．无割边集D．每条边都不是割边14．4个顶点的完全图G，其生成树个数是（）。

图论部分练习一、填空题1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是．2．设给定图G(如右由图所示)，则图G的点割集是．3．设G是一个图，结点集合为V，边集合为E，则G的结点等于边数的两倍．4．无向图G存在欧拉回路，当且仅当G连通且．5．设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等于，则在G中存在一条汉密尔顿路．6．若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为．7．设完全图Kn 有n个结点(n≥2)，m条边，当时，Kn中存在欧拉回路．8．结点数v与边数e满足关系的无向连通图就是树．9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树．10．设正则5叉树的树叶数为17，则分支数为i = ．二、判断说明题（判断下列各题，并说明理由．）1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．2．如下图所示的图G存在一条欧拉回路．3．如下图所示的图G不是欧拉图而是汉密尔顿图．G4．设G是一个有7个结点16条边的连通图，则G为平面图．5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．三、计算题1．设G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试(1) 给出G的图形表示； (2) 写出其邻接矩阵；(3) 求出每个结点的度数； (4) 画出其补图的图形．2．图G=<V, E>，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．3．已知带权图G如右图所示．(1) 求图G的最小生成树； (2)计算该生成树的权值．4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．四、证明题1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k 条边才能使其成为欧拉图．。

课前练习一、填空题1、图G 是简单图当且仅当 。

2、简单图G 是二部图当且仅当 。

3、若简单图G 满足(G)δ≥3，则G 中存在长度至少为 的圈。

4、连通图G 具有欧拉通路，而无欧拉回路的充要条件为 。

5、一颗树有两个2度分支点，一个3度分支点，三个4度分支点，则该树有 片树叶。

6、设T 为高为k 的二叉树，则T 最多有 个顶点。

7、设图G 是具有6条边、4个顶点的平面图,则图G 的面数为 。

8、一个图为非平面图当且仅当 。

9、S V ⊂，S 是图G 的极大独立集，则()V G S -是图G 的 。

10、带权为1，3，5，7，8，11，13的最优二叉树T 的权W(T)= 。

二、解答题1、求下图G 1的色多项式，并指出其色数、点连通度和边连通度。

图G 12、（1）证明自补图的阶数n 4k =或者n 4k 1=+，k 为某个自然数。

（2）找出所有4阶的自补图。

3、（1）证明：设G 是有v 个顶点ε条边，且G 是自对偶平面图，则2v 2ε=-。

（2）已知一颗无向树T 有三个3度结点，一个二度结点，其余都是1度结点。

①T 有几个1度结点？②试画出两棵满足上述度数要求的非同构的无向树。

4、通过布尔变量的运算，求下图3的全部极小支配集。

V 16 图3图G 25、用破圈法求下图G 3中的一颗最小生成树,写出具体过程，并计算生成树的权。

图G 36、设简单图,, |V|=n, |E|=m,G V E =<> 若有212n m C -≥+，则G 是哈密尔顿图。

7、证明：5K 不是平面图.8、证明：若,(,1)m n K m n ≥是哈密顿图，则必有.m n = 9、若,m n K 是树，求,m n 应满足的条件.132411253e 6e 1e 2e 3e 4e 5e 7e 8e 9。

⽹络流24题题解⽹络流24题by ctldragon到⽬前为⽌，还有数字梯形问题和机器⼈路径规划问题未完成。

⽹络流24题主要考建模，算法都不难（餐⼱计划问题显然要拆点，把⼀天拆成早上和晚上。

源点 s 向每天晚上连⼀条容量为所需餐⼱数，费⽤为 0 的边，表⽰获得脏餐⼱。

每天早上向汇点 t 连⼀条容量为所需餐⼱数，费⽤为 0 的边，表⽰提供⼲净餐⼱。

每天晚上可以向第⼆天晚上连⼀条容量为 inf ，费⽤为 0 的边，表⽰将脏餐⼱留在第⼆天。

i −m 天向 i 天连⼀条容量为 inf ，费⽤为 f 的边，表⽰快洗。

i −n 天向 i 天连⼀条容量为 inf ，费⽤为 s 的边，表⽰快洗。

然后就愉快的跑最⼩费⽤最⼤流了。

远古代码：by ctldragon s 0t 0inf 0i −m i inf f i −n i inf s #include<bits/stdc++.h>#define re register#define int long longusing namespace std;const int inf=0x3f3f3f3f;int n;int p,ft,fcost,st,scost;int s,t;struct node{int v,nxt,flow,dis;}a[1000000];int head[20000],cnt=1;void add(int u,int v,int flow,int dis){a[++cnt].v=v;a[cnt].flow=flow;a[cnt].dis=dis;a[cnt].nxt=head[u];head[u]=cnt;}int dis[20000],pre[20000];bool vis[20000];bool SPFA(){queue<int>q;memset(vis,false,sizeof vis);memset(pre,0,sizeof pre);while(!q.empty())q.pop();for(re int i=0;i<=2*n+1;i++)dis[i]=inf;dis[s]=0;vis[s]=true;q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=false;for(re int i=head[u];i;i=a[i].nxt){int v=a[i].v;if(!a[i].flow)continue;if(dis[v]>dis[u]+a[i].dis){dis[v]=dis[u]+a[i].dis,pre[v]=i;if(!vis[v])vis[v]=true,q.push(v);}}}if(dis[t]==inf)return 0;return 1;Processing math: 44%n 个⽉之前的代码了，码风极其奇怪/kk家园 / 星际转移问题⾸先并查集判断⼀下地球和⽉球是否连起来，没连起来就是⽆解。

一般图论与连通性-练习题Problem A. 老乡问题描述“老乡见老乡两眼泪汪汪，问一问老乡你过得怎么样？心情好不好啊做工忙不忙？其实我和你一样夜夜梦故乡。

老乡见老乡两眼泪汪汪，问一问老乡你又要去何方？吃过多少苦啊受过几回伤？其实我和你一样总想闯一闯。

他乡的话你你你会不会讲，他乡的歌你你你爱不爱唱？习不习惯飘泊的生活，想不想念自己的家乡？他乡的话你你你会不会讲，他乡的歌你你你爱不爱唱？有没有钱寄给你爹娘，想没想过何时回故乡？……”《老乡》唱出了很多20世纪九十年代打工创业者的心声，歌曲一经发行，便传遍大江南北。

其实，老乡的范围可大可小。

比如在省里看到同一县的人，在市里看到同一区的人，在全国看到同一省的人，都可以算做老乡。

在农村或小县城的日常口语中，老乡一般也能用作关系亲密的兄弟之间的一种称呼。

现在给定称作老乡的若干人员对，请您做出判断给定任何两人是否是老乡。

输入有若干组测试数据。

每组测试数据的第一行是2个整数n，q (0 ≤ n ≤ 10000，q<10) ，即是老乡的人数对。

接下来有n行，每行是一个用空格隔开的数对A 和B，表示A和B是老乡，(A ≠ B, 1 ≤ A, B ≤ 100000) 。

接下来有q行，每行有两个整数x和y。

两组数据之间有一个空行。

输出对每组测试数据，先输出“Case #”，换行，其中#是测试数据序号（从1开始）。

接着对q组整数x和y，一行输出x与y是否是老乡的结论：如是，则输出“YES”，否则输出“NO”。

输入样例4 21 23 45 61 61 41 54 21 23 45 67 81 41 5输出样例Case 1 NO YES Case 2 NONO Case 3 NO YESProblem B. 一笔画问题描述一笔画回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。

现给定一个图，问是否存在一笔画回路？输入测试输入包含若干测试用例。

每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。

网络与图论内容：①中国邮递员问题；--欧拉图②旅行商问题；--汉密尔顿图③考试安排问题；--图的顶点着色班级：试1202寂寞男孩队本堂课我们组只针对性介绍以下的三个问题；（其它相关性知识可能介绍不全）①中国邮递员问题；②旅行商问题；③考试安排问题以下先介绍一些基础的图论的基本概念：定义7-1.1 图G由一个三元组<V(G), E(G) , ϕG>表示，其中：非空集合V(G)={v1,v2,…,vr} 称为图G的结点集，其成员vi(i=1,2,…,r)称为结点或顶点；集合 E(G)={e1,e2,…,es} 称为图G的边集，其成员ej(j=1,2,…s)称为边。

函数ϕG ：E(G)→(V(G),V(G)) ，称为边与顶点的关联映射。

点的度数的定义：在图G=<V，E>，v∈V，与结点v关联的边数称为该点的度数，记为deg(v)。

中国邮递员问题背景：一个邮递员从邮局出发投递信件，他必须在所管辖范围内的所有街道至少走一次，最后回到邮局。

选择一条最短的路线完成投递任务。

中国邮递员问题实质上是讨论邮递员如何才能够走最短的路径去穿过每一个街道。

这样就涉及到了2种可能性，其一：邮递员不走重复的路就将所有的街道走一遍并且回到邮局。

这其实就是求无向欧拉回路的问题。

其二邮递员需要走过一条或多条的已经走过的路，但需要满足这几条重复的路路径最短，使他走完所有街道并回到邮局。

接下来我们讨论第一种情况：欧拉回路（欧拉图）如果无孤立结点图G上有一条经过G的所有边一次且仅一次的路径，则称该路径为图G的欧拉路（Euler walk）。

如果图G上有一条经过G边一次且仅一次的的回路，则称该回路为图G的欧拉回路，具有欧拉回路的图称为欧拉图判定以下的图是不是欧拉图：（2）（1）无向欧拉图有以下定理：无向图G具有一条欧拉回路，当且仅当G连通且所有结点度数皆为偶数。

（结点度数：在每个结点上有N条路相连就称结点度数为N）如果存在的这一条路是欧拉回路则邮递员所通过的最短路径就是所有路长的总和，即图中所有边长（权）的总和。

第十章 图与网络分析精典习题10.1 证明如下序列不可能是某个简单图的次的序列：（1）7,6,5,4,3,2 （2）6,6,5,4,3,2,1 （3）6,5,5,4,3,2,110.2 已知9个人921,,,v v v 中，1v 和两个人握过手， 32,v v 各和四个人握过手，7654,,,v v v v 各和五个人握过手，98,v v 各和六个人握过手，证明这九个人中一定可以找出三个人互相握过手。

10.3 有八种化学药品A 、B 、C 、D 、P 、R 、S 、T 要放进储藏室保管。

出于安全原因，下列各组药品不能储存在同一室内：A-R 、A-C 、A-T 、R-P 、P-S 、S-T 、T-B 、T-D 、B-D 、D-C 、R-S 、R-B 、P-D 、S-C 、S-D 问储存这八种药品至少需要多少间储藏室。

10.4 已知有十六个城市及他们之间的道路联系（见图10-1）。

某旅行者从城市A 出发，沿途依次经过J 、N 、H 、K 、G 、B 、M 、I 、E 、P 、F 、C 、L 、D 、O 、C 、G 、N 、H 、K 、O 、D 、L 、P 、E 、I 、F 、B 、J 、A ，最后到达城市M 。

由于疏忽，该旅行者忘了在图上标明各城市的位置，请应用图的基本概念及理论，在图10—1中标明各城市A~P 的位置。

10.5 十名研究生参加六门课程的考试。

由于选修的课程不同，考试门数也不一样。

表10—1给出了每个研究生应参加考试的课程（打Δ号的）。

规定考试应在三天内结束，每天上下午各安排一门。

研究生们提出希望每人每天最多考一门，又课程A 必须安排在每一天上午考，课程F 安排在最后一门，课程B 只能安排在中午考，试列出一张满足各方面要求的考试日程表。

表10-1图10-1e 1 v 1v 2v 3 v 4v 5v 6v 7v 8 v 9v 10e 2e 3 e 7e 4e 5e 6e 8e 9e 10 e 11e 12e 13e 14e 15图10-210.6 用破圈法和避圈法找出图10-2的一个支撑树。

第七章图与网络分析一、单项选择题1．关于可行流，以下叙述不正确的是（）A.可行流的流量大于零而小于容量限制条件B．在网络的任一中间点，可行流满足流人量=流出量C．各条有向边上的流量均为零的流是一个可行流D．可行流的流量小于或等于容量限制条件而大于或等于零2．关于最小树，以下叙述（）正确。

A.最小树是一个网络中连通所有点而边数最少的图B．最小树是一个网络中连通所有的点，而权数最少的图C．一个网络中的最大权边必不包含在其最小树内D．一个网络的最小树一般是唯一的。

3．最小树的算法关键是把最近的某些结点连接到那些已接结点上去，前者所指结点是（）A. 边缘结点B.未接结点C.已接结点D.最重要结点4.最小树问题就是在网络图中，找出若干条边，连接所有结点，而且（）A.连接的总长度最大B.连接的总长度最小C.连接的总长度为0D.计算总长度5．最小树问题就是在网络图中，找出若干条边，连接（）A.相邻结点B.头尾结点C.部分结点D.所有结点6．任一树中的边数和它的点数之间的关系是（）A.边数等于点数减1B.边数等于点数加1C.点数等于边数减1D.点数等于边数加1 7．最大流问题中，对于一个可行流，V i V j有向边上的流量f ij必须满足的条件之一是（）A.0≤f ij≥c ijB.0≥f ij≤c ijC. 0≤f ij≤c ijD. 0≥f ij≥c ij8.一个连通图中的最小树可能不唯一，其权（）A.是唯一确定的B.可能不唯一C.可能不存在D.一定有多个二、多项选择题1.关于图论中图的概念，以下叙述正确的的（）A.图中的边可以是有向边，也可以是无向边B.图中的各条边上可以标注权C.结点数等于边数的连通图必含圈D.结点数等于边数的图必连通E.图中的边只能是有向边2.关于最短路，以下叙述不正确的有（）A. 从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的B．从起点出发到终点的最短路是唯一的C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上D．从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上E．整个网络的最大权边的一定不包含在从起点到终点的最短路线上3.关于增广链，以下叙述正确的有（）A．增广链是一条从发点到收点的有向路，这条路上各条边的方向必一致B．增广链是一条从发点到收点的有向路，这条路上各条边的方向可不一致C．增广链上与发收点方向一致的边必是非饱和边，方向相反的边必是流量大于零的边 D．增广链上与发收点方向一致的边必是流量小于容量的边，方向相反的边必是流量等于零的边E．增广链上与发收点方向一致的边必是流量为零的边，方向相反边必是流量大于零的边4.在下图中，根据（a）生成的支撑树有（）三、应用题1.下图是6个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路的总长度最小，应如何做?最小的总长度是多少?2．对下面的连通图，试求出最小树。