作业帮关于图论中 最小路径覆盖的疑问
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/05/17 08:13:10
关于图论中 最小路径覆盖的疑问
我对于 最小路径覆盖的概念是在百度百科上看的 那边有提到了PXP的有向图 什么是PXP有向图呢?
最小路径覆盖=|P|－最大匹配数 这里的P是指 顶点个数吗?
其中最大匹配数的求法是把P中的每个顶点pi分成两个顶点pi'与pj'' 这句话不理解 一个顶点分成2个顶点是什么意思?
我对于 最小路径覆盖的概念是在百度百科上看的 那边有提到了PXP的有向图 什么是PXP有向图呢?
最小路径覆盖=|P|－最大匹配数 这里的P是指 顶点个数吗?
其中最大匹配数的求法是把P中的每个顶点pi分成两个顶点pi'与pj'' 这句话不理解 一个顶点分成2个顶点是什么意思?
百度百科我看了,好像解释得够清楚的.
关于什么是P×P,我也不知道（哦,大概是说,边是一个单纯的二元关系,即是有向的；如果是无向边,要求(u,v)=(v,u)）,不过在我看来这句话就是多余；
P表示顶点集,加绝对值的P就是指顶点个数；
对于有向图,把一个点u拆成两个点u1,u2,这是有向图化为无向图的常见方法,即：其中一个点u1作为有向边中,箭头开始的那个节点；一个点u2作为有向边中,箭头指向的那个节点.因此,对所有点都这样拆分后,u1只指向了u出边指向的那些点,u2只指向了u入边的那些点.整个有向图转化为一个无向的二部图,嗯.
关于什么是P×P,我也不知道（哦,大概是说,边是一个单纯的二元关系,即是有向的；如果是无向边,要求(u,v)=(v,u)）,不过在我看来这句话就是多余；
P表示顶点集,加绝对值的P就是指顶点个数；
对于有向图,把一个点u拆成两个点u1,u2,这是有向图化为无向图的常见方法,即：其中一个点u1作为有向边中,箭头开始的那个节点；一个点u2作为有向边中,箭头指向的那个节点.因此,对所有点都这样拆分后,u1只指向了u出边指向的那些点,u2只指向了u入边的那些点.整个有向图转化为一个无向的二部图,嗯.