下载文档原格式
《图论及其应用》习题课教材目录第一章图的基本概念1.1 图和简单图1.2 子图与图的运算1.3 路与图的连通性1.4 最短路及其算法1.5 图的代数表示及其特征1.6 极图1.7 交图与团图习题1第二章树2.1 树的概念与性质2.2 树的中心与形心2.3 生成树2.4 最小生成树习题2第三章图的连通度3.1 割边、割点和块3.2 连通度3.3 应用3.4 图的宽距离和宽直径习题3第四章欧拉图与哈密尔顿图4.1 欧拉图4.2 高效率计算机鼓轮的设计4.3 中国邮路问题4.4 哈密尔顿图4.5 度极大非哈密尔顿图4.6 旅行售货员问题4.7 超哈密尔顿图4.8 E图和H图的联系4.9 无限图中的欧拉,哈密尔顿问题习题4第五章匹配与因子分解5.1 匹配5.2 偶图的匹配与覆盖5.3 Tutte定理与完美匹配5.4 因子分解5.5 最优匹配与匈牙利算法5.6 匹配在矩阵理论中的应用习题5第六章平面图6.1 平面图6.2 一些特殊平面图及平面图的对偶图6.3 平面图的判定及涉及平面性的不变量6.4 平面性算法习题6第七章图的着色7.1 图的边着色7.2 顶点着色7.3 与色数有关的几类图7.4 完美图7.5 着色的计数，色多项式习题27.6 List着色7.7 全着色7.8 着色的应用习题7第八章Ramsey定理8.1 独立集和覆盖8.2 Ramsey定理8.3 广义Ramsey数8.4 应用习题8习题 11. 证明在n阶连通图中（1）至少有n-1条边。
（2）如果边数大于n-1，则至少有一条闭通道。
（3）如恰有n-1条边，则至少有一个奇度点。
证明(1) 若对∀v∈V(G),有d(v)≥2,则：2m=∑d(v)≥2n ⇒ m≥n>n-1,矛盾！若G中有1度顶点，对顶点数n作数学归纳。
当n=2时，G显然至少有一条边，结论成立。
设当n=k时，结论成立，当n=k+1时，设d(v)=1，则G-v是k阶连通图，因此至少有k-1条边，所以G 至少有k条边。
(2010-02-07 18:00:40)转载分类：ACM标签：杂谈最大流POJ 1273 Drainage DitchesPOJ 1274 The Perfect Stall (二分图匹配)POJ 1698 Alice's ChancePOJ 1459 Power NetworkPOJ 2112 Optimal Milking (二分)POJ 2455 Secret Milking Machine (二分)POJ 3189 Steady Cow Assignment (枚举)POJ 1637 Sightseeing tour (混合图欧拉回路)POJ 3498 March of the Penguins (枚举汇点)POJ 1087 A Plug for UNIXPOJ 1149 Pigs (构图题)ZOJ 2760 How Many Shortest Path (边不相交最短路的条数)POJ 2391 Ombrophobic Bovines (必须拆点，否则有BUG)WHU 1124 Football Coach (构图题)SGU 326 Perspective (构图题，类似于 WHU 1124)UVa 563 CrimewaveUVa 820 Internet BandwidthPOJ 3281 Dining (构图题)POJ 3436 ACM Computer FactoryPOJ 2289 Jamie's Contact Groups (二分)SGU 438 The Glorious Karlutka River =) (按时间拆点)SGU 242 Student's Morning (输出一组解)SGU 185 Two shortest (Dijkstra 预处理，两次增广，必须用邻接阵实现，否则 MLE) HOJ 2816 Power LinePOJ 2699 The Maximum Number of Strong Kings (枚举+构图)ZOJ 2332 GemsJOJ 2453 Candy (构图题)SOJ3312 Stockholm KnightsSOJ3353 Total FlowSOJ2414 Leapin' Lizards最小割SOJ3106 Dual Core CPUSOJ3109 Space flightSOJ3107 SelectSOJ3185 Black and whiteSOJ3254 Rain and FgjSOJ3134 windy和水星 -- 水星交通HOJ 2634 How to earn moreZOJ 2071 Technology Trader (找割边)HNU 10940 CoconutsZOJ 2532 Internship (找关键割边)POJ 1815 Friendship (字典序最小的点割集)POJ 3204 Ikki's Story I - Road Reconstruction (找关键割边) POJ 3308 ParatroopersPOJ 3084 Panic RoomPOJ 3469 Dual Core CPUZOJ 2587 Unique Attack (最小割的唯一性判定)POJ 2125 Destroying The Graph (找割边)ZOJ 2539 Energy MinimizationTJU 2944 Mussy Paper (最大权闭合子图)POJ 1966 Cable TV Network (无向图点连通度)HDU 1565 方格取数(1) (最大点权独立集)HDU 1569 方格取数(2) (最大点权独立集)POJ 2987 Firing (最大权闭合子图)SPOJ 839 Optimal Marks (将异或操作转化为对每一位求最小割)HOJ 2811 Earthquake Damage (最小点割集)2008 Beijing Regional Contest Problem A Destroying the bus stations ( BFS 预处理 )( ZOJ 2676 Network Wars (参数搜索)POJ 3155 Hard Life (参数搜索)ZOJ 3241 Being a Hero有上下界ZOJ 2314 Reactor Cooling (无源汇可行流)POJ 2396 Budget (有源汇可行流)SGU 176 Flow Construction (有源汇最小流)ZOJ 3229 Shoot the Bullet (有源汇最大流)HDU 3157 Crazy Circuits (有源汇最小流)最小费用流HOJ 2715 Matrix3HOJ 2739 The Chinese Postman ProblemPOJ 2175 Evacuation Plan (消一次负圈)POJ 3422 Kaka's Matrix Travels (与 Matrix3 类似)POJ 2516 Minimum Cost (按物品种类多次建图)POJ 2195 Going HomeBUAA 1032 Destroying a PaintingPOJ 2400 Supervisor, Supervisee (输出所有最小权匹配)POJ 3680 IntervalsHOJ 2543 Stone IVPOJ 2135 Farm TourBASHU2445 餐巾问题---------------------------------------------onmylove原创最大流题目：TC：Single Round Match 200 Round 1 – Division I, Level Three Single Round Match 236 Round 1 – Division I, Level ThreeSingle Round Match 399 Round 1 – Division I, Level Three 同Hoj1024:2003 TCO Semifinal Round 4 – Division I, Level Three 2004 TCCC Championship Round – Division I, Level Three 2005 TCO Sponsor Track Round 3 – Division I, Level One混合图的欧拉回路Poj1637: ：求增广边：Poj3204：类似：Hoj1082: &pid=6pku图论、网络流入门题总结、汇总(2009-10-07 23:25:25)转载分类：acm_图论题标签：杂谈POJ 2449 Remmarguts' Date(中等)题意：经典问题：K短路解法：dijkstra+A*(rec)，方法很多相关：该题亦放在搜索推荐题中POJ 3013 - Big Christmas Tree(基础)题意：最简单最短路，但此题要过，需要较好的程序速度和，还要注意精度解法：DijkstraPOJ 3463 - Sightseeing(中等)题意：最短路和比最短路大1的路的数量解法：需要真正理解dijkstraPOJ 3613 - Cow Relays(较难)题意：求经过N条边的最短路解法：floyd + 倍增，贪心POJ 3621 - Sightseeing Cows(中等)题意：求一个环路，欢乐值 / 总路径最大解法：参数搜索 + 最短路(ms 原始的bellman tle, 用spfa才过) POJ 3635 - full tank?(中等)题意：最短路变形解法：广搜相关：生成树问题基本的生成树就不放上来了POJ 1639 - Picnic Planning(较难)题意：顶点度数有限制的最小生成树解法：贪心 + prim/kruskalPOJ 1679 - The Unique MST(基础)题意：判断MST是否唯一解法：prim就行，不过还是易错的题POJ 2728 - Desert King(中等)题意：所谓最优比率生成树解法：参数搜索 + primPOJ 3164 - Command Network(难)题意：最小树形图解法：刘朱算法，这个考到的可能性比较小吧？POJ 3522 - Slim Span(基础)题意：求一颗生成树，让最大边最小边差值最小解法：kruskal活用连通性，度数，拓扑问题此类问题主要牵扯到DFS，缩点等技巧POJ 1236 - Network of Schools(基础)题意：问添加多少边可成为完全连通图解法：缩点，看度数POJ 1659 - Frogs' Neighborhood(基础)题意：根据度序列构造图解法：贪心，详细证明参见havel定理POJ 2553 - The Bottom of a Graph(基础)POJ 2186 - Popular Cows(基础)题意：强连通分量缩点图出度为0的点POJ 2762 - Going from u to v or from v to u?(中等)题意：单向连通图判定解法：缩点 + dp找最长链POJ 2914 - Minimum Cut(难)题意：无向图最小割解法：Stoer-Wagner算法，用网络流加枚举判定会挂POJ 2942 - Knights of the Round Table(难)题意：求双联通分量(或称块)中是否含奇圈解法：求出双连通分量后做黑白染色进行二分图图判定相关： 3177 - Redundant Paths(中等)POJ 3352 - Road Construction(中等)题意：添加多少条边可成为双向连通图解法：把割边分开的不同分量缩点构树，看入度建议对比下1236，有向图添加多少条边变成强连通图POJ 3249 - Test for Job(基础)解法：bfs / dfs + dpPOJ 3592 - Instantaneous Transference(基础)解法：缩点，最长路，少人做的水题，注意细节POJ 3687 - Labeling Balls(中等)解法：拓扑排序POJ 3694 - Network(中等)解法：双连通分量+并查集2-SAT问题此类问题理解合取式的含义就不难POJ 2723 - Get Luffy Out(中等)POJ 2749 - Building roads(较难)解法：二分 + 2-SAT判定POJ 3207 - Ikki's Story IV - Panda's Trick(基础) 解法：简单的2-sat，不过其他方法更快POJ 3648- Wedding(中等)解法：用2-sat做会比较有意思，但是暴搜照样0ms POJ 3678 - Katu Puzzle(基础)解法：直接按合取式构图验证就行了POJ 3683 - Priest John's Busiest Day(中等)解法：n^2枚举点之间的相容性构图，求解2-SAT最大流问题变形很多，最小割最大流定理的理解是关键POJ 1149 - PIGS(较难)绝对经典的构图题POJ 1273 - Drainage Ditches(基础)最大流入门POJ 1459 - Power Network(基础)基本构图POJ 1637 - Sightseeing tour(Crazy)题意：求混合图的欧拉迹是否存在解法：无向边任意定向，构图，详建黑书P324POJ 1815 - Friendship(中等)题意：求最小点割解法：拆点转换为边割相关： 1966 - Cable TV Network(中等)题意：去掉多少点让图不连通解法：任定一源点，枚举汇点求点割集(转换到求边割)，求其中最小的点割POJ 2112 - Optimal Milking(基础)二分枚举，最大流POJ 2391 - Ombrophobic Bovines(中等)题意：floyd, 拆点，二分枚举相关： 2396 - Budget(中等)题意：有源汇的上下界可行流解法：用矩阵-网络流模型构图，然后拆边相关：，最小割模型在竞赛中的应用POJ 2455 - Secret Milking Machine(基础)二分枚举，一般来说需要写对边容量的更新操作而不是每次全部重新构图POJ 2699 - The Maximum Number of Strong Kings(较难)解法：枚举人数 + 最大流(感谢xpcnq_71大牛的建图的提示)POJ 2987 - Firing(较难)题意：最大权闭包解法：先边权放大，第一问总量-最大流，第二问求最小割相关：&_c02_owner=1Profit(中等)最大权闭包图的特殊情况ZOJ 2071 - Technology Trader 也是此类型，懒了没做3084 - Panic Room(中等，好题)题意：略解法：根据最小割建模POJ 3155 - Hard Life(很挑战一题)题意：最大密度子图解法：参数搜索 + 最大权闭合图，的论文(nb解法)最小割模型在信息学竞赛中的应用一文中也有讲POJ 3189 - Steady Cow Assignment(中等)题意：寻找最小的区间完成匹配解法：这题充分说明SAP的强大，纯暴力可过。
=============================以下是最小生成树+并查集======================================【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)★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 Boys1150 Machine Schedule1151 Air Raid1179 Ollivanders: Makers of Fine Wands since 382 BC.1281 棋盘游戏1498 50 years, 50 colors1507 Uncle Tom's Inherited Land*1528 Card Game Cheater1845 Jimmy’s Assignment2063 过山车2119 Matrix2444 The Accomodation of Students2768 Cat vs. Dog3081 Marriage Match II3360 National Treasures1045 也可搜索1350 最小路径覆盖3118 类似二分匹配3729238910542819 完全匹配1668 二分+多重匹配3605 多重匹配3861 强连通+二分匹配2236 无题IIhdu3468hdu4185 奇偶匹配【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 one2448 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 强连通+并查集双连通：3694 Network 边双连通(同hdu2460)3177 Redundant Paths 构造边双连通3352 Road Construction 构造边双连通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 兹鼓欧拉回路19563472 混合欧拉【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 Reward3342 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============================以下是网络流系列============================ 【HDU】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-35291007 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. 在图论中，如果一个图的每个顶点的度数都是偶数，那么这个图一定存在欧拉路径吗？A. 是的B. 不一定C. 没有欧拉路径D. 无法确定答案：B2. 图论中的哈密顿路径是指什么？A. 经过图中所有顶点的路径B. 经过图中所有顶点的回路C. 经过图中某些顶点的路径D. 经过图中某些顶点的回路答案：A3. 如果一个图是完全图，那么它的边数是多少？A. 顶点数的一半B. 顶点数的平方C. 顶点数的两倍D. 顶点数减一答案：B二、填空题4. 在无向图中，如果存在一条路径，使得每个顶点只被经过一次，并且起点和终点相同，这样的路径被称为________。
答案：欧拉回路5. 图论中的二分图是指图中的顶点可以被分成两个不相交的集合，使得同一个集合内的顶点之间没有边，而不同集合之间的顶点之间有边，这种图也被称为________。
答案：二部图三、简答题6. 请简述图论中的最短路径问题，并给出解决该问题的一种算法。
答案：最短路径问题是在图中找到两个顶点之间的最短路径的问题。
解决该问题的一种算法是迪杰斯特拉算法（Dijkstra's algorithm），该算法通过维护一个顶点集合来记录已经找到最短路径的顶点，并迭代更新距离，直到找到从起点到所有顶点的最短路径。
7. 描述图论中的图着色问题，并说明其在实际生活中的应用。
答案：图着色问题是将图的顶点着色，使得任何两个相邻的顶点颜色不同。
在实际生活中，图着色问题可以应用于时间表的安排、频率分配、电路设计等领域，其中每个顶点代表一个任务或频道，而颜色则代表不同的时间段或频率。
结束语：以上是图论测试题及答案，希望能够帮助大家更好地理解和掌握图论的基本概念和算法。
图论试题及答案解析图片一、选择题1. 图论中，图的基本元素是什么？A. 点和线B. 点和面C. 线和面D. 点和边答案：A2. 在无向图中，如果两个顶点之间存在一条边，则称这两个顶点是：A. 相邻的B. 相连的C. 相等的D. 相异的答案：A3. 在有向图中，如果从顶点A到顶点B有一条有向边，则称顶点A是顶点B的：A. 父顶点B. 子顶点C. 邻接顶点D. 非邻接顶点答案：B4. 一个图的度是指：A. 图中顶点的总数B. 图中边的总数C. 一个顶点的边数D. 图的连通性答案：C5. 一个图是连通的，当且仅当：A. 图中任意两个顶点都是相邻的B. 图中任意两个顶点都可以通过边相连C. 图中任意两个顶点都可以通过路径相连D. 图中任意两个顶点都可以通过子顶点相连答案：C二、填空题1. 在图论中，一个顶点的度数是该顶点的________。
答案：边数2. 如果一个图的任意两个顶点都可以通过边相连，则称该图为________。
答案：完全图3. 一个图中，如果存在一个顶点到其他所有顶点都有边相连，则称该顶点为________。
答案：中心顶点4. 图论中，最短路径问题是指在图中找到两个顶点之间的________。
答案：最短路径5. 如果一个图的任意两个顶点都可以通过有向路径相连，则称该图为________。
答案：强连通图三、简答题1. 请简述图论中的欧拉路径和哈密顿路径的定义。
答案：欧拉路径是指在图中经过每条边恰好一次的路径，而哈密顿路径是指在图中经过每个顶点恰好一次的路径。
2. 什么是图的着色问题？答案：图的着色问题是指将图中的顶点用不同的颜色进行标记，使得相邻的两个顶点颜色不同。
四、计算题1. 给定一个无向图G，顶点集为{A, B, C, D, E}，边集为{AB, BC, CD, DE, EA}，请画出该图，并计算其最小生成树的权重。
答案：首先画出图G的示意图，然后使用克鲁斯卡尔算法或普里姆算法计算最小生成树的权重。
图论考试试题图论考试试题在计算机科学领域中，图论是一门重要的学科。
它研究的是图的性质和图上的算法。
图由节点和边组成，节点表示对象，边表示对象之间的关系。
图论可以应用于网络分析、社交网络、路径规划等领域。
图论的考试试题可以帮助学生加深对图论的理解和应用能力。
一、基本概念题1. 什么是图？答：图是由节点和边组成的数据结构。
节点表示对象，边表示对象之间的关系。
2. 图的分类有哪些？答：图可以分为有向图和无向图。
有向图的边有方向，无向图的边没有方向。
另外，图还可以分为加权图和非加权图。
加权图的边具有权重，非加权图的边没有权重。
3. 什么是路径？答：路径是图中连接两个节点的边的序列。
4. 什么是连通图？答：连通图是指图中的任意两个节点之间都存在路径。
二、算法题1. 广度优先搜索算法（BFS）是如何工作的？答：广度优先搜索算法从起始节点开始，逐层遍历图中的节点。
它首先访问起始节点的所有邻居节点，然后依次访问邻居节点的邻居节点，直到遍历完所有可达节点。
2. 深度优先搜索算法（DFS）是如何工作的？答：深度优先搜索算法从起始节点开始，沿着一条路径一直向下访问直到无法继续为止，然后回溯到上一个节点，选择另一条路径继续访问，直到遍历完所有可达节点。
3. 如何判断一个图是否是二分图？答：二分图是指可以将图中的节点分为两个独立的集合，使得同一集合中的节点之间没有边相连。
判断一个图是否是二分图可以使用染色法。
从任意一个节点开始，将其染成红色，然后将其邻居节点染成蓝色，再将邻居节点的邻居节点染成红色，以此类推。
如果在染色过程中发现相邻节点颜色相同，则该图不是二分图。
三、应用题1. 在社交网络中，如何找到两个人之间的最短路径？答：可以使用广度优先搜索算法来找到两个人之间的最短路径。
从一个人开始，逐层遍历其朋友圈中的人，直到找到目标人。
在遍历过程中，可以记录路径，最后得到最短路径。
2. 在电信网络中，如何找到两个城市之间的最短路径？答：可以使用迪杰斯特拉算法来找到两个城市之间的最短路径。
网络流建模汇总 by Edelweiss目录最大流 (4)《POJ 1149 PIGS》 (4)《POJ 1637 Sightseeing tour》 (8)《POJ 2391 Ombrophobic Bovines》 (9)《POJ 2699 The Maximum Number of Strong Kings》 (10)《POJ 3281 Dining》 (11)《JOJ 2453 Candy》 (11)《ZOJ 2760 How Many Shortest Path》 (12)《WOJ 1124 Football Coach》 (12)《SGU 326 Perspective》 (13)《SGU 438 The Glorious Karlutka River =)》 (14)《SPOJ 287 Smart Network Administrator》 (14)《SPOJ 962 Intergalactic Map》 (15)《小结》 (15)最小割 (15)《HOJ 2634 How to earn more》 (16)《HOJ 2713 Matrix1》 (16)《POJ 1815 Friendship》 (17)《ZOJ 2532 Internship》 (17)《Ural 1277 Cops and Thieves》 (18)《SPOJ 839 Optimal Marks》 (18)《SPOJ 1693 Coconuts》 (19)《Beijing Regional 2008 Problem A Destroying the bus stations》 (19)《小结》 (20)有上下界 (21)《POJ 2396 Budget》 (21)《小结》 (22)最小费用流 (22)《HOJ 2543 Stone IV》 (22)《HOJ 2715 Matrix3》 (23)《HOJ 2739 The Chinese Postman Problem》 (23)《POJ 3680 Intervals》 (24)《SPOJ 371 Boxes》 (24)《BASHU 2445 餐巾问题》 (25)《剪刀石头布》 (25)《小结》 (26)最大流《POJ 1149 PIGS》【题目大意】有M个猪圈，每个猪圈里初始时有若干头猪。
图论作业 1⼀、填空题1. ⾮同构的阶和阶树的个数分别为和⽅法：按照树中存在的最⻓路进⾏枚举 (从开始)注意：对于的树来说，路的最短⻓度为234 阶树2345 阶树2. 阶正则图的补图的边数为考点⼀：完全图每个点的度数是✨考点⼆：⼀个图和其补图的并是完全图⼀个点在原图和补图中的度数和为图是正则，那么图的补图为正则。
故补图的度数之和为根据握⼿定理：3. 设图中各顶点度数均为，且，则 n = ，m =考点：握⼿定理根据握⼿定理：4. 设简单图的邻接矩阵为，且则图的边数为考点：邻接矩阵的性质定理 10：令是⼀个有推⼴邻接矩阵的阶标定图，则的⾏列元素等于由到的⻓度为的途径的数⽬推论：设为简单图的邻接矩阵，则：的元素是的度数。
的元素是含的三⻆形的数⽬的两倍 （考过填空）5. 设是⼀个完全部图，是第部分的顶点数，则它的边数为考点：完全多部图的概念与结构完全部图的点数：；边数：（考过填空）6. 设是阶简单图，且不含完全⼦图，则其边数⼀定不会超过考点：Turán 定理定理 18 (T urán)：若是阶简单图，并且不包含，则边数。
此外，仅当时，✨计算公式：，则例：阶简单图，，则最多有条边例： 9 阶简单图，，则最多有 27 条边7. 设阶图是具有个分⽀的森林，则其边数为树的边数 = 顶点数 - 1森林的边数 = 顶点数 - 连通分⽀数8. ⼀棵树有个度为的结点，，则它有个度数为的顶点考点：握⼿定理 + 树的性质（边数 = 顶点数 - 1），其中由握⼿定理：故：整理得：9. 完全图的⽣成树的个数为定理 27：⼆、不定项选择题1. 关于图的度序列，下列命题正确的是（ABCD）A. 同构的两个图的度序列相同B. ⾮负整数序列是图的度序列当且仅当是偶数C. 如果正整数序列是⼀棵树的度序列且，那么序列中⾄少有两个D. 正整数序列是⾮平凡树的度序列当且仅当E. 若图的顶点度数之和⼤于等于图的顶点度数之和，则图度优于图❌F. 如果⾮负整数序列是简单图的度序列，那么在同构意义下只能确定⼀个图❌考点：度序列 && 图序列关系：简单图的度序列简称图序列注意：判断⾮负整数序列是否为简单图的度序列暂⽆好的⽅法，只有等价转换的⽅法A 显然正确（已经默认递增或递减排列）B 正确：定理 3：⾮负整数组是图的度序列的充分必要条件是：为偶数C 正确：定理 20：每棵⾮平凡树⾄少有两⽚树叶D 正确：存在⼀棵⾮平凡树，以该序列为度序列的充要条件握⼿定理E 错误：先有度弱或度优，才有度数之和⼩于或⼤于；反过来不成⽴F 错误：不⽌确定⼀个图2. 对于序列，下列说法正确的是（BD）A. 可能是简单图的度序列❌B. ⼀定不是简单图的度序列C. 只能是简单图的度序列❌D. 只能是⾮简单图的度序列E. 不是任意图的度序列❌考点：度序列 && 图序列对于简单图，顶点的最⼤度顶点数 - 1A 错B 对C 错：对于该题，⻓度为 6，说明有 6 个点，同时最⼤度为 7，显然不是简单图！！D 对E 错：定理 3：⾮负整数组是图的度序列的充分必要条件是：为偶数3. 下列说法错误的是（ACE）A. 若⼀个图中存在闭途径，则⼀定存在圈❌B. 偶图中不存在奇圈C. 若图不含三⻆形，则为偶图❌D. 图的顶点之间的连通关系⼀定是等价关系E. 存在每个顶点的度数互不相同的⾮平凡简单图❌A 错误：闭途径（），但不存在圈B 正确：定理 9：⼀个图是偶图当且仅当它不包含奇圈C 错误：可能存在⻓度不为 3 的奇圈，如 5，7 等等D 正确：即便在有向图中，也存在弱连通E 错误：定理 5：⼀个简单图的个点的度不能互不相同4. 关于简单图的邻接矩阵，下列说法错误的是（C）A. 矩阵的⾏和等于该⾏对应顶点的度数B. 矩阵的所有元素之和等于该图边数的倍C. 矩阵的所有特征值之和等于该图边数的倍❌D. 矩阵的所有特征值的平⽅和等于该图边数的倍E. 矩阵的主对⻆线的元素之和等于该图边数的倍F. 若是⾮连通图，则相似于某个准对⻆矩阵考点：简单图邻接矩阵的性质A 正确：矩阵的「⾏和」或「列和」等于该「⾏」或「列」对应顶点的度数B 正确：所有元素之和等于度数之和，根据握⼿定理判断正确C 错误：矩阵的所有特征值之和等于矩阵的迹；矩阵的迹⼜是矩阵主对⻆线上的元素之和；对于简单图，邻接矩阵主对⻆线元素均为D 正确：所有特征值的平⽅和等于的所有特征值之和；的迹就是主对⻆线之和，也就是图的所有度数之和，就等于边数的两倍E 显然正确F 正确：⽆法解释，因为不懂5. 图⼀定是树的是（BDE）A. 连通图❌B. ⽆回路但任意添加⼀条边后有回路的图C. 每对顶点间都有路的图❌D. 连通且E. ⽆圈且考点：树的基本性质A 错误：树是连通的⽆圈图B 正确：回路是边不重圈的并；⽆回路肯定⽆圈，加⼀条边有回路，肯定就有圈C 错误：每对顶点间存在唯⼀的⼀条路DE 显然正确三、解答题1. 设⽆向图 有条边， 度与 度顶点各 个，其余顶点度数均⼩于 ，问 中⾄少有⼏个顶点？在顶点数最少的情况下，写出 的度序列，该度序列是⼀个图序列吗？考点：握⼿定理 + 图序列解：由于求顶点数量最少，故假设 0 度顶点为 0 个，1 度顶点为 0 个，同时设 2 度顶点有 个根据握⼿定理得：；解得：所以 中⾄少有 7 个顶点；图 的度序列为 根据 Havel-Hakimi 定理，可得下⾯推导过程：显然 是可图的，所以 是可图的2. 证明整数序列是简单图的度序列，并构造⼀个对应的简单图。
