LoginSignup
0
0

グラフ

Posted at

Graph definition and terminologies

Term Definition
Adjacent Nodes Two nodes are adjacent if there exists an edge between them.
Path A sequence of connected nodes.
Simple Path A path where each node appears at most once.
Cycle A path that starts and ends at the same node.
Simple Cycle A cycle where each node, except the first and last, appears at most once.
Connected Graph A graph where there exists a path between every pair of distinct nodes.
Disconnected Graph A graph with at least two disjoint subgraphs.
Connected Component A connected subgraph within a disconnected graph.
Complete Graph A graph where every pair of distinct nodes is connected by an edge.
Subgraph A graph that is derived from another graph by selecting a subset of its vertices and edges.
Weighted Graph A graph where each edge is assigned a weight.
Directed Graph (Digraph) A graph where edges have a direction specified.
Directed Edge An edge in a directed graph with a specified direction.
Predecessor and Successor In a directed graph, if (x, y) is a directed edge, y is a successor of x and x is a predecessor of y.

グラフの用語と定義

名前 定義
隣接ノード エッジが存在する場合、2つのノードは隣接しています。
パス 接続されたノードのシーケンス。
単純パス 各ノードが最大1回だけ現れるパス。
サイクル 始点と終点が同じノードであるパス。
単純サイクル 最初と最後以外の各ノードが最大1回だけ現れるサイクル。
連結グラフ すべての異なるノード間にパスが存在するグラフ。
非連結グラフ 少なくとも2つの分離した部分グラフを持つグラフ。
連結成分 非連結グラフ内の連結部分グラフ。
完全グラフ すべての異なるノードの間にエッジが存在するグラフ。
サブグラフ 別のグラフから選択した頂点と辺の部分集合によって派生したグラフ。
重み付きグラフ 各エッジに重みが割り当てられたグラフ。
有向グラフ(ダイグラフ) エッジに方向が指定されているグラフ。
有向エッジ 特定の方向を持つ有向グラフ内のエッジ。
先行点(predecessor)後続点(successor)  有向グラフ内で、(x、y)が有向エッジの場合、yはxの後続者(successor)であり、xはyの先行点(predecessor)であると言います。
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0