无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。  

含有n个顶点的无向完全图有n×(n-1)/2条边。

含有n个顶点的有向完全图有n×(n-1)条边。

顶点的度：在无向图中，顶点v的度是指依附于

顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；

顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。

该顶点的边数，通常记为TD (v)。

在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系：
 

在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系：

回路（环）：第一个顶点和最后一个顶点相同的路径。

简单路径：序列中顶点不重复出现的路径。

简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。

子图：若图G=（V，E），G'=（V'，E'），如果: V'ÍV 且E' Í E ，则称图G'是G的子图。

连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。

连通分量：非连通图的极大连通子图称为连通分量。

一个n个顶点的连通无向图，其边的个数至少为（ n-1   ）

因为它如果是个树的话，边就最少了

连通（Connected）

• 无向图中的连通：在无向图中，如果任意两个顶点之间存在一条路径，那么这个图就是连通的。即从一个顶点出发，可以通过边访问到任何其他顶点。

• 有向图中的连通：在有向图中，如果从任意两个顶点中的一个可以通过有向边到达另一个，那么这两个顶点是连通的。但需要注意，这并不意味着整个图是连通的，仅是针对特定的顶点。

强连通（Strongly Connected）

• 有向图中的强连通：在有向图中，如果图中的每一对顶点  都能相互到达，那么这个图是强连通的。强连通要求顶点之间的路径是双向的。

• 对于无向图，强连通的概念并不适用，因为无向图的每条边本身就是双向的，通常直接称为“连通”。

总结

• 连通：在无向图中，任意两个顶点都有路径相连；在有向图中，特定的两个顶点之间有一条路径。
• 强连通：仅适用于有向图，表示任意两个顶点之间既可以从一个到达另一个，也可以从另一个到达前者。

要连通具有n个顶点的有向图，至少需要（   n-1 ）条边。

只要连通就行，不用强连通。所以画个单边的树就行

由握手定理知A正确，

在无向图中，握手定理表述为：所有顶点的度数之和等于边数的 2 倍。

通俗来讲，假如把图中的顶点看成是人，边看成是两个人握手，那么每个人握手的次数（即顶点的度数）加起来，就等于总的握手次数的 2 倍，因为每一条边（一次握手）会在两个顶点（两个人）的度数中各被计算一次。

BC错误，画个单边树，得到b错误，画个三角形得到c错误。

图的遍历

① 在图中，如何选取遍历的起始顶点？

在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。然后选取下标小的顶点

② 从某个起点始可能到达不了所有其它顶点，怎么办？

解决方案：多次调用从某顶点出发遍历图的算法。

③ 因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环?

解决方案：附设访问标志数组visited[n] 。

④ 在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？

解决方案：深度优先遍历和广度优先遍历。

邻接矩阵的DFS和BFS：

#include<iostream>
using namespace std;
int visited[10] = { 0 };

class MGraph
{
public:
	MGraph(char a[], int n, int e);
	~MGraph() {};
	void DFS(int v);
	void BFS(int v);
private:
	char vertex[10];
	int edge[10][10];
	int vertexNum, edgeNum;

};

MGraph::MGraph(char a[], int n, int e)
{
	int i, j, k;
	vertexNum = n;
	edgeNum = e;
	for (i = 0; i < vertexNum; i++)
		vertex[i] = a[i];
	for (i = 0; i < vertexNum; i++)
		for (j = 0; j < vertexNum; j++)
			edge[i][j] = 0;
	for (k = 0; k < edgeNum; k++)
	{
		cin >> i >> j;
		edge[i][j] = 1;
		edge[j][i] = 1;
	}
}

void MGraph::DFS(int v)
{
	int  j;
	cout << vertex[v];
	visited[v] = 1;
	for(j =0;j<vertexNum;j++)
		if (edge[v][j] == 1 && visited[j] == 0)
			DFS(j);
}

void MGraph::BFS(int v)
{
	cout << vertex[v];
	visited[v] = 1;
	int w, j, Q[10];
	int front = -1, rear = -1;
	Q[++rear] = v;
	while (front != rear)
	{
		w = Q[++front];
		for(j = 0;j<vertexNum;j++)
			if (edge[w][j] == 1 && visited[j] == 0)
			{
				cout << vertex[j];
				visited[j] = 1;
				Q[++rear] = j;
			}
	}
}

int main()
{
	int i;
	char ch[] = { 'A','B','C','D','E' };
	MGraph MG(ch, 5, 6);
	for (i = 0; i < 10; i++)
		visited[i] = 0;
	cout << "深搜：" << endl;
	MG.DFS(0);
	for (i = 0; i < 10; i++)
		visited[i] = 0;
	cout << endl;
	cout << "广搜" << endl;
	MG.BFS(0);
}

邻接表：

#include<iostream>
using namespace std;
int visited[10] = { 0 };

struct EdgeNode
{
	int adjvex;
	EdgeNode* next;
};

struct VertexNode
{
	char vertex;
	EdgeNode* firstEdge;
};

class ALGraph
{
public:
	ALGraph(char a[], int n, int e);
	~ALGraph() ;
	void DFS(int v);
	void BFS(int v);
private:
	VertexNode adjlist[10];
	int vertexNum, edgeNum;
};

ALGraph::ALGraph(char a[], int n, int e)
{
	int i, j, k;
	EdgeNode* s = nullptr;
	vertexNum = n;
	edgeNum = e;
	for (i = 0; i < vertexNum; i++)
	{
		adjlist[i].vertex = a[i];
		adjlist[i].firstEdge = nullptr;
	}
	for (k = 0; k < edgeNum; k++)
	{
		cin >> i >> j;
		s = new EdgeNode;
		s->adjvex = j;
		s->next = adjlist[i].firstEdge;
		adjlist[i].firstEdge = s;
	}
}

ALGraph::~ALGraph()
{
	EdgeNode* p = nullptr, * q = nullptr;
	for (int i = 0; i < vertexNum; i++)
	{
		p = q = adjlist[i].firstEdge;
		while (p != nullptr)
		{
			p = p->next;
			delete q;
			q = p;
		}
	}
}

void ALGraph::DFS(int v)
{
	int j;
	EdgeNode* p = nullptr;
	cout << adjlist[v].vertex;
	visited[v] = 1;
	p = adjlist[v].firstEdge;
	while (p != nullptr)
	{
		j = p->adjvex;
		if (visited[j] == 0)
			DFS(j);
		p = p->next;
	}
}

void ALGraph::BFS(int v)
{
	int w, j, Q[10];
	int front = -1, rear = -1;
	EdgeNode* p = nullptr;
	cout << adjlist[v].vertex;
	visited[v] = 1;
	Q[++rear] = v;
	while (front != rear)
	{
		w = Q[++front];
		p = adjlist[w].firstEdge;
		while (p != nullptr)
		{
			j = p->adjvex;
			if (visited[j] == 0)
			{
				cout << adjlist[j].vertex;
				visited[j] = 1;
				Q[++rear] = j;
			}
			p = p->next;
		}
	}
}

int main()
{
	int i;
	char ch[] = { 'A','B','C','D','E' };
	ALGraph ALG(ch, 5, 6);
	ALG.DFS(0);
	for (i = 0; i < 10; i++)
		visited[i] = 0;
	cout << endl;
	ALG.BFS(0);
}