导向图是图形吗？

Question

我遇到了Sipser对计算理论介绍的（指示）图的定义，第二版。

在pp.10上 无向图, ，或者只是一个 图形, ，是一组点，线连接了一些点。这些点称为节点或顶点，线称为边缘，...

在同一页上，

在任何两个节点之间不允许一个边缘.

在第12页上，

如果它具有箭头而不是线，则图是一个 定向图,...

在第12页的图0.16中，有一个有向图的示例，从节点1到节点2的箭头和从节点2到节点1的箭头。

因此，我们在两个节点之间的两个方向上有两个箭头。

我了解所有这些基础知识。

我的问题是，

导向图是图形吗？

Answer 1

通常，使用正式定义很有帮助：

令$ v $有限套件。 $ g =（v，e）$是

• 一个 图形 如果$ e subseteq left { {v_1，v_2 } mid v_1，v_2 in v right } $和
• 一个 Digraph 如果$ e subseteq left {（v_1，v_2） mid v_1，v_2 in v right } $。

注意中心差：边缘以图形和对设置为digraphs。特别是，这个定义暗示了简单性。扩展定义也很容易：如果$ e $是多键，则可能具有非简单图形。如果边缘具有两个以上的组件，则会有超图。

免责声明： 人们以不同的方式定义（DI）图；这是一种非常普遍的变体。例如，如果您对Digraphs不舒服（正式）不是图形，则可以这样定义它们：

令$ v $有限套件和$ e subseteq v^2 $。我们称这对$ g =（v，e）$ a 图形. 。我们说

• $ g $是 无方向 如果且仅当$（v_1，v_2） in E longleftrightarrow（v_2，v_1） in E $和
• $ g $是 指导 否则。

这将无向图定义为有向图的特殊情况。请注意，通过此定义，扩展到 标记 图（边缘获得标记）可能很尴尬：我们希望完整的挖掘图与完整的无向图不同（因为前者之间的每对节点之间有两个标记的边缘，后者只有一个）；根据这个定义，它们是相同的。请注意，我给出的第一个定义如何很好地阐明了这个问题；有时，定义是（重新）考虑以后的需求。

Answer 2

“图”一词具有两种含义：它可以是“无向图”（例如书籍定义的方式）的速记，或者可以指代“图形般”的东西，例如有指导性或无向图。第一个含义最常见。

有向图和无方向的图不是同一件事（箭头与线路），尽管如果您将每个（无向）的边缘替换为两个箭头，则可以将无向图视为有向图，一个方向一个方向（因此A -B变为a <a < - > b）。

此外，对于某些问题，您可以将有向图转换为相似的无向图，您的问题具有相同的解决方案。汉密尔顿循环问题在无向图上是NP-HARD的证明通常是通过将有名的图形转换为无方向的图，而当原始图具有一个时，该图将有指导版本的降低来完成。