当前位置 博文首页 > smilejiasmile的博客:离散结构:图论与树
〉 柯尼斯堡七桥问题的解决是图论创立的标志
〉 1736年欧拉在发表的论文中证明七桥无法仅走一遍能遍历七座桥,并提出和解决了“一笔画”问题。
〉 欧拉将现实问题抽象为平面上的点和线的组合,并通过讨论点的奇偶性来判定能否遍历
〉 于是欧拉便创建了两个新的学科:图论 和 拓扑学
〉 由结点和联结结点的边所构成的离散结构
〉 记做 G = <V, E>
〉 结点 vertex 集V:非空集合
〉 边 edge集 E:多重集合(集合中可能存在相同元素,元素附带一个重数的属性)
〉 边集是多重集合表示图可以有多个相同的边。
注:所谓的多重集合就是指同一个集合中允许出现多个相同的元素。因为在一个集合中,相同的
cs