英文链接源链接 [19515]
contenteditable="true"

Graph Theory - Introduction 介绍

在数学和计算机科学领域,图论是研究与边和顶点之间的关系有关的图。它是一门受欢迎的学科,在计算机科学,信息技术,生物科学,数学和语言学等领域都有应用。事不宜迟,让我们从定义图表开始。

什么是图?

图形是一组对象的图形表示,其中一些对象对通过链接连接。相互连接的对象由称为顶点的点表示,连接这些顶点的链接称为边。

形式上,图是一对集合(V,E),其中 V 是顶点集合,而 E 是边集合,连接成对的顶点。看一下下图-

Graph Example

在上图中,

V = {a,b,c,d,e}

E = {a,b,ac,bd,cd,at}

图论的应用

图论在工程的各个领域都有其应用-

  • 电气工程-图论的概念广泛用于设计电路连接。连接的类型或组织称为拓扑。拓扑的一些示例是星形,桥接,串联和并行拓扑。

  • 计算机科学-图论用于算法研究。例如,

    • Kruskal算法
    • Prim算法
    • Dijkstra的算法
  • 计算机网络-网络中互连的计算机之间的关系遵循图论的原理。

  • 科学-图形表示一种物质的分子结构和化学结构,一种生物的DNA结构等。

  • 语言学-语言的解析树和语言的语法使用图。

  • 常规-城市之间的路线可以使用图形表示。描述诸如家庭树之类的分层有序信息可以用作称为树的特殊类型的图。

点我分享笔记