Python
 Computer >> コンピューター >  >> プログラミング >> Python

指定された頂点の次数がPythonのグラフまたはツリーを表すかどうかを確認します

いくつかの頂点の次数のリストがあるとします。グラフとツリーのどちらを形成しているかを確認する必要があります。

したがって、入力がdeg =[2,2,3,1,1,1]のような場合、出力はTree

になります。

指定された頂点の次数がPythonのグラフまたはツリーを表すかどうかを確認します

これを解決するには、次の手順に従います-

  • vert：=頂点の数
  • deg_sum：=すべての頂点のすべての度の値の合計
  • 2 *（vert-1）がdeg_sumと同じ場合、
    • 「ツリー」を返す
  • 「グラフ」を返す

理解を深めるために、次の実装を見てみましょう-

サンプルコード

def solve(deg):
   vert = len(deg)
   deg_sum = sum(deg)
     
   if 2*(vert-1) == deg_sum:
      return 'Tree'
   return 'Graph'

deg = [2,2,3,1,1,1]
print(solve(deg))

入力

[2,2,3,1,1,1]

出力

Tree

  1. 与えられたグラフがPythonで2部グラフであるかどうかをチェックするプログラム

    無向グラフが1つあるとすると、グラフが2部グラフであるかどうかを確認する必要があります。グラフのすべてのエッジ{u、v}がAに1つのノードuを持ち、Bに別のノードvを持つように、グラフのノードを2つのセットAとBに分割できる場合、グラフは2部グラフであることがわかります。 したがって、入力が次のような場合 次に、出力はTrueになり、[0,4]はセットAにあり、[1,2,3]はセットBにあり、すべてのエッジはAからAまたはBからBではなく、AからBまたはBからAになります。 。 これを解決するために、次の手順に従います- 関数dfs（）を定義します。これはソースを取ります

  2. 特定のバイナリツリーがPythonのヒープであるかどうかを確認します

    二分木があるとしましょう。ヒープかどうかを確認する必要があります。ヒープには次のプロパティがあります。ヒープはバイナリツリーになります。そのツリーは完全なツリーである必要があります（つまり、最後を除くすべてのレベルがいっぱいである必要があります）。そのツリーのすべてのノード値は、その子ノード（max-heap）以上である必要があります。 したがって、入力が次のような場合 その場合、出力はtrueになります これを解決するには、次の手順に従います- 関数number_of_nodes（）を定義します。これが定着します rootがnullの場合、 0を返す それ以外の場合、