加权图形问题，TRUE/FALSE +说明

我试图得到一些真实/虚假的问题。我很担心，当我用真的回答他们中的许多人时...请假设所有图都是无向并且做不是有不同重量。负重量应该没问题。如果G具有唯一最重边e的循环，则e不能成为任何MST的一部分。加权图形问题，TRUE/FALSE +说明

我的回答是错误的。例如，我们具有节点A，B，C，d的曲线图，E.

AB = 1 
BC = 2 
BD = 3 
CD = 100 
DE = 4

正如你可以看到，BCD是一个循环。我的观点是，由于它是一个循环，我们可以通过采取其他路线，始终避免唯一最重要的边缘CD。所以这是真的。我的论点是否听起来（足够）？

Qb）由Dijkstra算法计算出的最短路径树必然是MST。

我的回答是真实的，但我的直觉告诉我有什么不对。那么...... Disjkstra和Prim都是贪婪算法。他们每次都会选择最轻的加权边缘。是否有任何情况下，最短路径树是不是最小生成树？我其实很难理解这两个家伙之间的区别。 QP）Prim的算法与负加权边缘一起工作。

我的回答是错误的。因为这就是wiki所说的......：p 该算法是关于找到所有边缘中成本最低的边缘。所以负加权边缘应该不重要，是吗？但是负加权周期呢？如果G具有唯一最轻边e的循环，则e必须是每个MST的一部分。

我的回答是错误的。我们必须访问MST中的所有节点。例如，在一个长度为3的循环中，我们总是可以遍历该循环中的所有节点，分2步。如果有一个独特的最轻边缘，我们肯定会在MST中选择它。

我的声明是否正确？也许他们不够？那么有什么建议吗？

来源

2011-10-29 Felastine

dijstra用于计算A到B之间的最短路径。它不是MST。 Prim是MST。 – Bytemain

是的，但是在Dijkstra被执行之后，如果我们在到达目标时不停下来，我们会得到每个节点的最短路径。有时，问题甚至没有给出目标，这意味着我们继续迭代直到遍历所有节点。之后，我们有最短路径的树。问题是这个最短路径树是否在同一个图的MST中？ – Felastine

这是真的，但图中也有多个MST。 – Bytemain

对b）的建议：你的直觉说它是错的，所以试着构造一个反例。如果你找到一个，那么它就已经解决了，否则你通常可以通过分析你的反例构建失败的原因来看到为什么一个声明是真实的。不过，我并没有告诉你你的答案或你的直觉是否正确。

的功课肯定，是由于不久前，所以答案：

QA）如果G有一个独特的最重的边e一个周期，那么E不能有任何MST的一部分。

是的。假设您有一棵包含边缘e的生成树T。如果从树中删除边缘e，则会得到一个包含两个非空连接组件C1和C2的图。循环中至少有一个其他边必须连接C1和C2（否则它不会成为一个循环）。让g成为这样一个优势。通过删除e从T获得的树T'并且添加g是具有比T小的权重的生成树。因此T不是MST。

Qb）由Dijkstra算法计算出的最短路径树必然是一个MST。

我的回答是真实的，但我的直觉告诉我有什么不对。

本能是对的，那是错误的。考虑

6 
    A---B 
3 | | 1 
    C---D 
    3

其中最短路径树从顶点A计算。最短路径树是

6 
    A---B 
3 | 
    C---D 
    3

与总重量12，但独特的MST是

A B 
3 | | 1 
    C---D 
    3

体重7

QC）Prim算法可与负加权边缘。

是的。从正确权重的正确性推导出的一种方式是向所有边添加恒定权重W，以便所有边权重为正（例如W = 1 + max { |weight(e)| : e ∈ E }）。

由于具有V顶点的树总是具有V - 1边缘，任何生成树的总权重由改性和未改性的权重之间(V - 1)*W不同，所以树是MST对于修改的权重，当且仅当它是一个用于未修改的边权重。

通过为所有权重添加常数，不会改变按重量计算的边的排序，因此Prim算法会针对修改后的边权重构建与未修改的权重相同的生成树。

由于正权重的正确性，由修正权重的Prim算法构造的树是修改权重的MST。

Qd）如果G具有唯一最轻边e的周期，那么e必须是每个MST的一部分。

假。考虑

 1 1 
    A---B---C 
    |/\ | 
1 | /4 5\ | 1 
    |/ 6 \| 
    D-------E

BDE具有重量4的一个独特的最轻的边缘BD，但MST不含有该周期的边缘的周期。

如果图中的G，必须，然而，是每个MST的一部分，一个独特的最轻的边缘e。这与a）是双重的：考虑G的生成树T，其不包含e。通过将e添加到T，我们获得必须有循环的图T'（因为T是生成树并且e不在T中）。 T'中的任何周期必须包含e，否则这将是T中的周期。因此，选择中的任何一个循环T'（只有一个，但并不重要），并从C中删除除e以外的任何边缘。让结果图为T''。

T''的总重量小于T的总重量，因为T''从T获得，用较轻的一个替代边缘。连接了T''（因为它是通过去除周期的边从T'获得的），并且包含V顶点和V - 1边。因此它是一棵生成树，因此T不是最小的。

来源

2011-10-29 12:15:50

D为真。 Q）如果G具有唯一最轻边e的循环，则e必须是每个MST的一部分。真正。

轻边缘=穿过切口的边缘，其重量最小为穿过切口的任何边缘。假设（为了矛盾的目的）T'是G的不同MST。由于T和T'不是同一棵树，并且它们都有| V | -1边，在T中存在一些不在T'中的边e。从T中删除边e诱导（创建）G的切割;由于T是一棵生成树，删除e将G划分为两个不相交的顶点集合，它们一起包含了G的所有顶点，这正是切割的结果。现在，由于T是MST，边e必须是该切割上的（唯一的）光边缘，因此在每个MST中。但通过建设，边e不在T'。因此T'不是MST，与我们原来的假设相矛盾。

来源

2012-10-18 07:41:11 ealeon

加权图形问题，TRUE/FALSE +说明

回答

相关问题