图论中关于图的定义是什么
图论的解释 用数学方法 研究 “图”的一门新兴数学分支。所谓“图”，是指由一些点及连接其中某些点的线段构成的图形，用来表示具有 某种 二元关系的集合，因此它是处理离散数学模型的一种有力工具。图论的起源可 追溯 到18世纪关于七桥 问题 的研究。20世纪中期 随着 电子 计算 机的应用迅速发展。与运筹学、信息论、 控制 论等有密切联系，在科学技术和经济学等诸多 领域 有 广泛 应用。 词语分解 图的解释 图 （图） ú 用绘画表现出来的形象：图画。图案。图谱。图鉴。 指地图：《亚洲略图》。 图穷匕见 。 画：画影图形。 计谋，计划：宏图（亦作“弘图”、“鸿图”）。良图。 谋取， 希望 得到：图谋。图利。企图。 论的解释 论 （论） ù 分析 判断 事物的 道理 ：论断。论点。论辩。论据。论者。 议论 。 讨论 。辩论。 分析阐明事物道理的 文章 、理论和言论：理论。舆论。专论。社论。 学说，有系统的主张：系统论。 看待：一概而论。 衡量
图论基础
图 是由顶点V和边E的集合组成的二元组，记G=(V,E) 有向图、无向图、有权图、无权图、连通图（联通分量）、二分图 顶点的 度 （无向图种与顶点相连的边的数目）、 入度 （有向图中以该顶点为终点的边的数目）、 出度 （有向图中以该顶点为起点的边的数目），度等于入度和出度之和，所有边的入度和=所有边的出度和=边数 图的定义是指将边作为一个集合，从而允许两个无向边具有相同的端点。对于两个有向边可以有相同的起点和终点。这种边称为 平行边 或者 多重边 。另一种边的特殊类型是顶点和自己连接，也就是说两个顶点重合，我们称这样的边为 自循环 。除了少数例外，图没有平行边和自循环 图G中从顶点u到顶点v有一条路径，我们称u到达v，并且v是从u 可达 的。在无向图中，可达性的概念是对称的。 如果一个图是 连通 的，则意味着对于任何两个顶点，它们中间都是有路径的。 如果对于G的任何两个顶点u和v，都有u可达v并且v可达u，则有向图是 强连通 的 图G的 子图 是顶点和边是G的顶点和边的各自的子集的图H。G的 生成子图 是包含图G的所有顶点的图。 如果图G是不连通的，它的最大联通子图称为G的连通分支。 森林 是没有循环的图。 树 是连通的森林，即没有循环的联通图。图的 生成树 是树的生成子图 特性1 ：如果G是由m条边和顶点集V的图，那么 ，即边对顶点度数的总贡献度是边数目的两倍 特性2 ：如果G是有m条边和顶点集V的有向图，那么 即边对它的起点u的出度贡献了一个单元，对终点v的入度贡献了一个单元。因此边对顶点出度的总贡献和边的数目相等，入度也是一样。 特性3 ：给定G为具有n个顶点m条边的简单图。如果G是无向的，那么 ，如果G是有向的，那么 特性4： 给定G是有n个顶点和m条边的无向图。 边列表 ：对所有边采用无序的列表。但是没有有效的办法找到特定的边(u,v)，或者将所有的边入射到顶点v 邻接列表 ：为每个顶点维护一个单独的列表，包括入射到顶点的那些边。可以通过取较小集合的并集来确定完整的边集合，也可以更高效地找到所有入射到给出顶点的边 邻接图 ：和邻接列表非常相似，但是所有入射到顶点的边的次级容器被组织成一个图，而不是一个列表，用相邻的顶点作为键。这允许在O(1)的时间内访问特定的边(u,v) 邻接矩阵 ：对于有n个顶点的图维持一个n*n矩阵来提供最坏的情况下访问特定边(u,v)的时间O(1)。每一项专用于为顶点u和v的特定对存储一个参考边(u,v)；如果没有这样的边存在，该表项即为空 可能是最简单的，但不是最有效的。所有顶点存储在一个无序的列表V中，并且所有的边对象存储在一个无序的列表E中 将图形的边存储在较小的位置来对其进行分组，从而和每个单独的顶点相关联的次级容器结合起来。具体的，对每个顶点v维持一个集合l(v)，该集合被称为v的 入射 列表，其中全部都是入射到v的边。（在有向图的情况下，输出边和输入边分别存储在两个单独的集合lout(v)和lin(v)中。 同时要求邻接列表的基本结构在某种程度上保持顶点集合V，因此可以在O(1)时间内为给出的顶点v找出次级结构l(v) 命题 ：对于i=1，...，n，当且仅当有向图 从 到 有一条有向路径时，有向图 有边 ，其中中间的顶点在集合 中，特别的， 和 相等， 是 的传递闭包 该命题为计算G的依赖于一系列界限的每个 传递闭包提出了一个简单算法。这个算法被称为 Floyd_Warshall算法 没有有向循环的有向图被叫作 有向非循环图 ，或者简称 DAG
