离散数学实验报告四——图的应用

预习内容：

1.图的基本概念

1.1图的定义：现实世界中许多现象能用某种图形表示,这种图形是由一些点和一些连接两点间的连线所组成。

1.2邻接点: 同一条边的两个端点。

1.3孤立点: 没有边与之关联的结点。

1.4邻接边: 关联同一个结点的两条边。

1.5孤立边: 不与任何边相邻接的边。

1.6自回路（环）：关联同一个结点的一条边（（v，v）或〈v，v〉）。

1.7平行边(多重边):关联同一对结点的多条边。

2. 图的矩阵表示

2.1邻接矩阵：设G＝〈V ,E〉是有n个结点的简单图，则n阶方阵Ａ＝（aij）称为G的邻接矩阵。

2.2可达性矩阵：设G＝〈V ,E〉是一个有n个结点的有向图，则n阶方阵Ｐ＝（pij）称为图G的可达性矩阵。

实验目的与要求（及主要实验仪器、设备）：

1.通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算；

2. 通过实验提高学生编写实验报告、总结实验结果的能力；

3. 使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。

实验环境：软件：vc++6.0 ，硬件：电脑

实验原理（方法与与原理分析）：

一个图G是一个序偶〈V(G), E(G)〉，记为G＝〈V(G), E(G)〉。其中V(G)是非空结点集合， E(G)是边集合，对E(G)中的每条边，有V(G)中的结点的有序偶或无序偶与之对应。
在完全m叉树中，若树叶数为 t，分枝点数为 i，则 (m-1)i＝t-１
设有一棵二叉树，有ｔ片树叶。使其树叶分别带权w1， w2， …， wt的二叉树称为带权的二叉树。

实验步骤（程序代码与实验过程）：

#include<stdio.h>

#define BIG 9999

void dijkstra(int cost[][6], int n, int st, int distance[])

{ int s[6];

int mindis, dis;

int i, j, u;

for (i = 0; i < n; i++)

{

distance[i] = cost[st][i];

s[i] = 0;}

s[st] = 1;

for (i = 0; i < n; i++)

{ mindis = BIG;

for (j = 0; j < n; j++)

{if (s[j] == 0 && distance[j] < mindis)

{ mindis = distance[j];

u = j;

}

}

for (j = 0; j < n; j++)

{if (s[j] == 0)

{dis = distance[u] + cost[u][j];

distance[j] = (distance[j] < dis) ? distance[j] : dis;}}

s[u] = 1;}}

void main()

{ int y, j;

char* vertex[6] = { “V1”,“V2”,“V3”,“V4”,“V5”,“V6” };

int cost[6][6];

for (y = 0; y < 6; y++)

{for (j = 0; j < 6; j++)

{cost[y][j] = BIG;}}

int start, end, weight, i;

{ scanf_s("%d", &weight);

}

printf(“输入定点以及边的权重:”);

for (i = 0; weight != 0; i++)

{scanf_s("%d,%d,%d", &start, &end, &weight);

cost[start - 1][end - 1] = weight;

cost[end - 1][start - 1] = weight;}

int distance[6];

int s, e;

printf(“输入起始节点和最终节点，计算其最小距离（输入的数字不超过6，以逗号分隔）:”);

scanf_s("%d,%d", &s, &e);

dijkstra(cost, 6, s - 1, distance);

printf("%s---->%s %d\n", vertex[s - 1], vertex[e - 1], distance[e - 1]);}

实验结果（数据分析与结论）

：

离散数学实验报告四——图的应用

问题讨论：

问：如果使用计算机使用其加法指令，可用其计算3个数之和，那么如果要计算9个数X1,X2,…,X9之和，其至少要执行几次加法指令？

答：

由 (m-1)i＝t-１

可得(３-１)i＝９-１

得 i＝４

综上所述至少要执行 4 次加法指令。

离散数学实验报告四——图的应用