2024_CUMCM图论模型
目录
【2024_CUMCM】图论模型
基本概念
注：以下叙述大多是自话，夹杂多数不专业表述
点集、边集
图论中图是由 点 和 边 组成的
G(V,E)
V–点集
E–边集
权
G(V,E,W)
W–权
一般都有权，构成赋权图
赋权图
在图中每条边都赋予一个非负实数权重的图，就是给每一条边加上一个数
有向图、无向图
在图中就是表示为有没有箭头，边有箭头就是有向图，边没有就是无向图
邻接关系、关联关系
前者是点与点或边与边是否相邻。如果两个顶点之间存在一条边，则它们被认为是邻接的。
后者是点与边的关系。
完全图
每对不同的顶点之间都恰好有一条边相连的图。
n个点的任意两个点都有一边，即为n阶完全图
二部图（偶图）
直接看图示，比较清晰
二部图：分两部分，每部分每一个顶点相邻，两部分的顶点都对应有边
星图、扇图、轮图
树图
哈密顿圈
指的是从一个顶点出发，经过图中每个其他顶点恰好一次，然后返回到起点的闭合路径。
旅行售货员问题
应用在 旅行售货员问题 ，找到一个路径，使得旅行商从一个点出发，经过所有点恰好一次，并回到起点，且总权值最小
邻接矩阵
无向图
用1和0表示，相邻（有边）为1
有向图
看箭头是谁到谁，1->3,a13=1,a31=0
赋权图
遵循
对角全为0
如果图里面有边 ，起到终方向，如a13=7，a31=无穷
如果图里面两点没有边，直接无穷
关联矩阵
基本与邻接矩阵同理，不再赘述