1-1

无向连通图至少有一个顶点的度为1

错误：

无向连通图考点：

1. 每条边连接两个顶点，所有顶点的度之和等于边数的2倍

2.记住两个特殊的无相连通图模型：

A：B：

 

 1-2

用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。

错误：

这是邻接矩阵的特性。

 

 

---

 

 2-1

若无向图G =（V，E）中含10个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是

 

竞赛图（强连通）边数 = n(n-1)/2 = 45;

从其中任意拿走一个点，边数 -9，这个时候，任意增加一条边，这条边都是与多余的那个点相连的，此时图一定联通，ans = 45 - 9+1 = 37;

 

2-2

给定一个有向图的邻接表如下图，则该图有__个强连通分量

 

1.强连通分量：有向图中的极大强连通子图称作有向图的强连通分量.

2.第1点中的极大强连通子图：把图的所有结点用最少的边将其连接起来的子图.

3.一个顶点也是极大强连通子图.

 

 如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通

画图如下

 

 

 单个顶点也是强联通分量，或者是两两有路径连接的图的子集也是强联通分量；

2-6

如果G是一个有36条边的非连通无向图，那么该图顶点个数最少为多少？

 

无向竞赛图阶：	1	2	3	4	5	6	7	8	9
边数：	0	1	3	6	10	15	21	28	36

 

        有向图就*2;

 对于36条边来说，9个点一定是竞赛图：强连通图十个点，可以满足，一个点被孤立，成为非强连通图的情况；

2-14

        下列关于无向连通图特征的叙述中，正确的是： (2分)

1. 所有顶点的度之和为偶数
2. 边数大于顶点个数减1
3. 至少有一个顶点的度为1

这道题需要对连通图的性质理解，

1.度 = 2*边数 ，显然是偶数

2.边数大于等于顶点个数减一

3.sample，最上面让记住的两个图之一

 

 

2-19

一个有N个顶点的强连通图至少有多少条边？

 

最少还是最上面的例子，三角形，3个点，3条边，方向都为一个时针的方向，

想让边数多，那就选择竞赛图，最多n*（n+1）

 

 

 2-24

下列选项中，不是下图深度优先搜索序列的是

 

 

脑子代码任选一个跑一下；

 

2-29

图的广度优先遍历类似于二叉树的：

 

前序：一条路走到黑（dfs）

层次：雨露均沾（bfs）

 2-37

给定一有向图的邻接表如下。若从v1开始利用此邻接表做广度优先搜索得到的顶点序列为：{v1, v3, v2, v4, v5}，则该邻接表中顺序填空的结果应为

画图：

邻接表：解释下：5 - 2 之间右边， 5-4之间有边，不是 5 -2 有边 ， 2 - 4有边！

 

 

 

 

---

 

 

2-1

给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：

 

 这种题目，推荐的做法是跑代码，容我实现下10:58:34

11:20:28

 没毛病，代码贴上：

#include
       
        using  namespace std;#define INF 0x3f3f3f3fconst int maxn = 117;int m[maxn][maxn];int vis[maxn], low[maxn];/*对于这道题目来将，m就是临接矩阵，vis是访问标记数组，low是最短距离数组*/int n;int prim(){    vis[1] = 1;    int sum = 0;    int pos, minn;    pos = 1;    for(int i = 1; i <= n; i++)    {        low[i] = m[pos][i];    }    /*    先把第一个点放到树里，然后找到剩下的点到这个点的距离    */    for(int i = 1; i < n; i++)//循环遍历 n-1 次数，把点全部加入！    {        minn = INF;        for(int j = 1; j <= n; j++)        {            if(!vis[j] && minn > low[j]) //没有进树的节点，并且这个节点到树里面 点距离最近，拉进来            {                minn = low[j];                pos = j;            }        }        sum += minn;        vis[pos] = 1;        for(int j = 1; j <= n; j++)        {            if(!vis[j] && low[j] > m[pos][j])//用新加入的点，更新low值            {                low[j] = m[pos][j];            }        }    }    return sum;}void init(){    memset(vis,0,sizeof(vis));    memset(low,0,sizeof(low));    for(int i = 1; i <= n ;i++ )    for(int j = 1; j <= n; j++)        m[i][j] = INF;}void in_map(){    printf("输入邻接矩阵阶：\n");    scanf("%d",&n);    printf("输入邻接矩阵，无穷用 -1代表！\n");    int t;    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++)    {        scanf("%d",&t);        m[i][j] = (t==-1?INF:t);    }}int main(){    init();    in_map();    printf("%d",prim());}
       

 

 翘代码5分钟，输入2分钟差不多； = 7分钟；

 

7-4 排座位（25 分）

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

输入格式：

输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2 关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式：

对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but...；如果他们之间只有敌对关系，则输出No way。

 

#include
       
        using namespace std;int father[105];int maps[110][110];int n, m , k;int finds(int x){    if(x!=father[x]) father[x]=finds(father[x]);    return father[x];}void combine(int x,int y,int t){    if(t==1)    {        int a=finds(x);    int b=finds(y);    if(a==b)        return;    if(a
        
         >x>>y;        if(finds(x)==finds(y)&&maps[x][y]!=-1)        {            printf("No problem\n");        }        else if(finds(x)==finds(y)&&maps[x][y]==-1)        {            printf("OK but...\n");        }        else if(finds(x)!=finds(y)&&maps[x][y]==-1)        {            printf("No way\n");        }        else            printf("OK\n");   }}
        
       

　　

 

---

 

 最短路，所有的题目，基于代码：

 

 

 

 

 

---

 

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

(1) 选择一个入度为0的顶点并输出之；

(2) 从网中删除此顶点及所有。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有”信息，否则输出的顶点序列就是一种拓扑。

 

 

具体还是需要用具体题目来理解。

       

#include 
         
          using namespace std;#define maxn 100//可以根据题目条件进行更改int edge[maxn][maxn];int book[maxn];int point_num;int edge_num;bool check_point(int v)//确定这个点是不是没有入度；{    for(int i=1;i<=point_num;i++)        if(edge[i][v]==1&&(i!=v))//如果有入度，返回false,i==v时没有啥实际意义        return false;    return true;}void del_edge(int v)//删除以这个点为起始点的所有边{    fill(edge[v],edge[v]+point_num,0);//fill灵活用法，用for循环效果一样，时间复杂度相同}int main(){    memset(book,0,sizeof(book));    scanf("%d",&point_num);    scanf("%d",&edge_num);//点的个数，边的个数，设为宏观变量，比较好操作    memset(edge,0,sizeof(edge));         for(int i=1;i<=edge_num;i++)    {        int s_point,e_point;        scanf("%d%d",&s_point,&e_point);        edge[s_point][e_point]=1;    }    int i;//下面循环代码肯定是能优化的，不过我一时半会想不起来，欢迎留言，私信我    for(;i<=point_num;i++)    {        if(check_point(i)&&book[i]==0)        {            book[i]=1;            cout<
          <<" ";            del_edge(i);//删除bian            i=1;        }    }    for(int i=1;i<=point_num;i++)    {        if(book[i]==0)            cout<<
         

　　

2-5

对下图进行拓扑排序，可以得到不同的拓扑序列的个数是： 

 

1.    a入度为 0 ，出 a

2.   b 和 e 入度为 0

3.    假设出 e ， 后面只有一种方法 b c d

4.    假设出 b ，然后可以选择出 c/e   ，出 c，然后一定是 e d，出 e ，然后一定是 c d

总 3 种

 

 

理解，不推荐记忆，非重要考点： 

 

 

---