“图”这个词在数学中至少有两种含义。
在初等数学中,“图”指的是函数图或“函数的图”,即绘图。
在数学家的术语中,图是点和连接其中一些(可能是空的)子集的线的集合。图的点最常被称为图的顶点,但也可能被称为“节点”或简称为“点”。 类似地,连接图的顶点的线最常被称为图的边,但也可能被称为“弧”或“线”。
对图的研究被称为图论,最早由 D. König 在 20 世纪 30 年代系统地研究(Gardner 1984, p. 91)。 不幸的是,正如 Gardner (1984, p. 91) 指出的,“用‘图’这个术语来描述顶点和边的网络,与解析几何的‘图’[即函数绘图]相混淆,令人遗憾,但这个术语已经沿用下来。” 一些教育工作者使用术语“顶点-边图”来表示一组连接的节点,试图保留“图”的常用用法,即函数的绘图。
欧拉对所谓的欧拉环在柯尼斯堡所有七座桥梁上不存在的证明,现在被称为柯尼斯堡桥问题,是图论的著名先驱。 事实上,对图中各种路径(例如,欧拉路径、欧拉环、哈密顿路径和哈密顿环)的研究在现实世界问题中有很多应用。
图有各种不同的类型。 最常见的类型是图中最多一条边(即一条边或没有边)可以连接任意两个顶点。 这样的图被称为简单图。 如果允许顶点之间有多条边,则该图被称为多重图。 通常不允许顶点自连接,但有时会放宽此限制以允许这种“图的环”。 可能包含多条边和图的环的图称为伪图。
可以使用谓词在Wolfram 语言中测试对象是否为图GraphQ[g]。
图的边、顶点或两者都可以分配特定的值、标签或颜色,在这种情况下,该图被称为标记图。 顶点着色是将标签或颜色分配给图的每个顶点,使得没有边连接两个颜色相同的顶点。 类似地,边着色是将标签或颜色分配给图的每条边,使得相邻的边(或界定不同区域的边)必须接收不同的颜色。 基于一组指定的标准将标签或颜色分配给图的边或顶点的过程称为图着色。 如果不允许标签或颜色,使得边和顶点除了其内在的连通性之外不携带任何额外的属性,则该图被称为未标记图。
图的边也可以赋予方向性。 其中边是无向的普通图被称为无向图。 否则,如果在图的边的一个或两个端点上放置箭头以指示方向性,则该图被称为有向图。 其中每条边都被赋予唯一方向的有向图(即,边不能是双向的并且同时指向两个方向)称为定向图。 图或有向图以及将正实数分配给每条边的函数(即,定向边标记图)被称为网络。
非常令人惊讶的是,对于任何简单图,奇顶点(即,在其上入射了奇数条边的顶点)的数量始终是偶数。
可以在图的集合上定义大量运算。 例如,可以定义图的和、差、幂、并和积,以及图的特征值。
形式上,图可以被认为是更一般的CW-复形的一维情况。