有向グラフは、それが有効なツリーであるためにどのような特性を持たなければならないか？

Question

私はアルゴリズムを求めていません、私は定義を求めています。この質問

があります：given a graph to detect if it is a tree or not in directed and undirected graphs?が選択した回答によると、私は次のを思い付いた：

1. ：

   有向グラフの場合、有効な木であることを、それはすべての事実を満たさなければなりませんグラフは純粋に出て行くエッジを持つ頂点が1つだけでなければなりません。

2. グラフが接続されています。
3. このグラフの無向バージョンにはサイクルがありません。

私はこれをオンラインで検索し、ほとんどの人がこれらの点に同意したようです。

しかし、私はまだ混乱しています。たとえば、以下のグラフは？：

G1有効な木です：

G2：はい場合

、なぜ？いいえ、なぜですか？

ご協力いただきましてありがとうございます。ありがとう！

Answer 1

直接描画グラフの場合は、出力エッジを持つ頂点から開始します。私たちがトラバーサルをして、そこに未訪問の頂点があれば、それは木ではありません。
グラフG1については、
から始めることができます。
Aから始めると、Bを訪れる機会はありません。A→C、C→DまたはC→E。
Bから始めると、A. B→C、C→DまたはC→Eにアクセスする機会はありません。
Cと同じですが、AとBを訪れる機会はありません。
これは、各頂点を訪問する方法がないため、ツリーではないことを意味します。グラフは接続されていません。我々はAから起動した場合我々は、AまたはB
から開始することができます
グラフG2の場合
は、その後、このグラフでもあり、BとDのためB.
ため
同じケースを訪問する機会がありません接続されていません。