河把该城分成两部分，河中有
两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？
例2：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？
用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。
例3：哈密顿（Hamilto
）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。
例5电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。
例6设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设
备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表
年份
1
2
3
4
5
年初价格11
11
12
12
13
设备维修费如下表
使用年数01
12
23
34
45
每年维修费5
6
8
11
18
用
例8、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1…v7表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。
例9某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到销售点，这个网络的一部分如下图所示。由于管道直径的变化，各段管道（vivj）的流量cij（容量）也是不一样的。cij的单位为万加仑小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？
f例10由于输油管道的长短不一，所以在例6中每段管道（vivj）除了有不同的流量限制cij外，还有不同的单位流量的费用bij，cij的单位为万加仑小时，bij的单位为百元万加仑。如图。从采地v1向销地v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。
fr