- 集合
- グラフ
- 多重グラフ
- 順序対
- 有効グラフ
- 部分集合
- 部分グラフ
- 写像
- グラフの同型
- 集合の和, 積
- 次数
- 有効グラフの次数
- 正則グラフ
- 歩道, 道, 閉路
- 有向道, 有向閉路
- 切断点, 橋
- 内素な道
- 距離, 直径
集合：異なるものの集まり
Pythonには組み込み関数としてset()が用意されている。これは集合という意味であり、データは{}（波括弧）に囲われて表現される。また集合ではデータが一意に扱われる。
X = {"a", "b", "c"}
print(type(X))
# <class 'set'>
Y = ["a", "a", "b", "c"]
print(set(Y))
# {"a", "b", "c"}上記のように集合Yにaが2つ含まれている、重複している場合はset()により一意なデータとして変換される。ここで集合に格納された値のことを要素、あるいは元という。ここでは「a, b, c」が要素である。また、要素が一つもないことを空集合といい、要素数が有限の場合は有限集合、無限の場合は無限集合と呼ぶ。
集合はX = {1, 2, 3, 4}のように要素を表現することもあるが、要素の性質を用いてX = {x|xは4以下の自然数}と表すこともできる。Pythonで表すとおおよそ以下で正しいだろう。またn元集合とは要素数をnとした時の有限集合のことである。
X = {1, 2, 3, 4}
X = lambda x: True if x <= 4 else False- 集合
- 要素, 元
- 空集合
- 有限集合
- 無限集合
- n元集合
グラフ : 頂点と辺からなるもの
グラフとは頂点（点）の集合（頂点集合）と辺の集合（辺集合）によって構成される。頂点集合、辺集合がともに有限であるものを有限グラフという。グラフの頂点の数は位数と呼ばれ、グラフの辺の数はサイズと呼ばれる。
以下はグラフを通しての理解が効率的だと判断したため箇条書きで記している（太字部分が新しい用語）。カッコの中は各用語の説明である。
- aとbは隣接（辺を成している）
- cとdは非隣接（辺を成していない）
- 辺adの端点は頂点a, d（辺を構成している頂点）
- 頂点dの近傍は頂点a, b（自身の頂点と辺を成している頂点）
- 頂点aに接続している辺は、ab, ac, ad（自身が辺を構成する一部である）
- グラフ
- 頂点, 点, 端点
- 頂点集合
- 辺集合
- 有限グラフ
- 位数
- サイズ
- 隣接する
- 接続する
- 近傍
多重グラフ : 多重辺やループを許したグラフ
多重辺とは2頂点を結ぶ辺が2本以上ある辺のこと。例えば頂点a, bで辺を成すものが2本あり、それぞれの辺の名前を「A, B」としたとき「A, B」はともに多重辺である。つまり、辺を構成する端点が同一のものが2本以上ある場合のこと。次にループだが、これは端点が同じ辺のこと。また、多重辺やループを持たないグラフを単純グラフ、あるいは単にグラフと呼ぶ。定義2のグラフは単純グラフである。
- 多重辺
- ループ
- 多重グラフ
- 単純グラフ
順序対 : 決められた順序に並べられた対象の対
順序対は(a, b)で表され、a, bそれぞれを第一成分、第二成分と呼ぶ。aとbの値が異なる場合(a, b)と(b, a)は異なる順序対である。順序対とは要するに、多重グラフにおける多重辺に順序が加えられたものだと考えればよい。また、(a, a)となる順序対も存在する。
順序対は次の定義5で扱われる。
a = 10
b = 20
X = (a, b)
Y = (b, a)
print(X == Y)
# False- 順序対
有向グラフ : 辺に向きのあるグラフ
辺に向きのあるグラフのことを有向グラフ（ダイグラフ）と呼び、頂点集合と弧（有向辺）と呼ばれる頂点の順序対の集合（弧集合）によって構成される。
有向グラフに対して、向きのないグラフを無向グラフ、あるいは単にグラフと呼ぶ。これまで扱っていたのは無向グラフである。上の図で(a, b)と(b, a)は順序対であり、第一成分は始点、第二成分は終点とよばれる。また、(a, b)と(b, a)は対象弧でもある。さらに、同一の(始点、終点)を持つ2本以上の弧を多重弧と呼ぶ。ここでは(d, a)の弧が2本あるため、これは多重弧である。
多重弧やループを許した有向グラフを多重有向グラフ、あるいは多重ダイグラフと呼び、多重辺やループを持たないグラフを単純有向グラフ、あるいは単に有向グラフ（ダイグラフ）と呼ぶ。上の図は多重有向グラフである。また。定義2のグラフに順序がついたものが単純有向グラフである。
- 有向グラフ, ダイグラフ
- 弧, 有向辺
- 弧集合
- 無向グラフ
- 始点
- 終点
- 対象弧
- 多重弧
- 多重有向グラフ, 多重ダイグラフ
- 単純有向グラフ
以下のAは要素として1, 3, 5を有しており、BはAの要素に加え、2, 4の要素を有している。この時BはAの要素を含んでおり、これをAはBの部分集合であると表現する。また、空集合は任意の集合の部分集合である。
A = {1, 3, 5}
B = {1, 2, 3, 4, 5}
C = A & B
print(A == C)
# True- 部分集合
部分グラフ : 元となるグラフの一部となるグラフ
部分グラフとは、元となるグラフがあり、その一部であるグラフのこと。とくに、頂点が完全に一致しているものを全域部分グラフと呼ぶ。さらに誘導部分グラフとは、ある頂点を基準にしたときに、その頂点が構成する辺が、すべて元のグラフに含まれている時を指す。
- 部分グラフ
- 全域部分グラフ
- 誘導部分グラフ
写像 : 集合から集合へ要素を対応させること
上の図をもとに写像について説明する。集合Xは要素{A, B, C, D}を有している。集合Yは要素{1, 2, 3}を有している。ここでは分かりやすくするために、結婚相手を考えるものとする。集合Xは女性の集団であり、呼称を各要素に「さん」をつけて呼ぶこととする（例：Aさん）。集合Yも同様の呼称とする。この時、例えばAさんは1さんと結婚したいと考えており、これは以下のプログラムでのAさんの値1と対応する。この値を使い(A, 1)とすることをAから1への写像という。ここでは左から右への向きを持つ。
次に、2さんは自分と結婚したい人がいるかどうか確認したいとする。その場合は、自分の「2」という名前を使い、女性の集団から自分と結婚したい人を探すことになる。そうするとBさんとDさんがいることになる。矢印とは逆方向（右から左）から「対応する要素が存在すること」を上への写像という。
次に、集合Xのどの2個の要素も集合Yの異なる要素に対応するとき、つまり結婚相手がかぶらないとき、XからYへの1対1の写像という。ここでは集合XからAさんとBさんで1対1の写像となっている。
# 女性視点の結婚したいリスト
# key : 女性
# value: 結婚したい男性
women_ideal = {
"A": 1,
"B": 2,
"C": 3,
"D": 2,
}
# 男性
men = {1, 2, 3}
for man in men:
for woman, ideal in women_ideal.items():
if ideal == man:
print(f"{man}さんと結婚したい人には{woman}さんがいる")
# - Result -
# 1さんと結婚したい人にはAさんがいる
# 2さんと結婚したい人にはBさんがいる
# 2さんと結婚したい人にはDさんがいる
# 3さんと結婚したい人にはCさんがいる- 写像
- 上への写像
- 1対1の写像
グラフの同型 : 「同一」の頂点を持ち、同一の辺の繋がり方をしているグラフ
グラフを並び変えたり、回転させたりすることで、同じグラフが存在する場合のこと。以下のグラフで左のグラフと真ん中のグラフは同型ではなく、同型なのは左と右のグラフである。
また、以下のグラフは片方を並び変えることで、もう片方のグラフと同じ形を作ることができるため同型である。
- 同型
この定義10のプログラムでは、以下のモジュールを共通して使う。
import matplotlib.pyplot as plt
import networkx as nx集合Aと集合Bに対して、和集合とは集合Aと集合Bのいずれかに属している要素全体からなる集合のこと。
また積集合とは、集合Aと集合Bの両方に属している要素全体からなる集合のこと。
集合Aと集合Bの積集合が空集合であるとき、これらは互いに素であるという。
以下のプログラムで、C1はA1とB1の和集合である。D2は、A1とB1の積集合であるが、空集合であるため、A1とB1は互いに素であるといえる。
また、C2はA2とB2からなる積集合であり、互いに素ではない。
A1 = {1, 2, 3}
B2 = {4, 5, 6}
C1 = A1 | B2
D2 = A1 & B2
print(C1) # {1, 2, 3, 4, 5, 6}
print(D2) # {}
A2 = {1, 2, 3, 4, 5}
B2 = {3, 4, 5, 6, 7}
C2 = A2 & B2
print(C2) # {3, 4, 5}以下の画像で完全グラフについて考える。 完全グラフは、異なる2頂点がすべて隣接しているグラフのこと。 それぞれの頂点は隣接しており、1つだけの頂点を持つ部集合であるといえる。 この時のグラフは頂点数5つのクリークであるという。クリークは、完全グラフと同型な部分グラフの頂点集合のことである。
definition_src/complete_graph.py
graph_data = {
1: [2, 3, 4, 5],
2: [1, 3, 4, 5],
3: [1, 2, 4, 5],
4: [1, 2, 3, 5],
5: [1, 2, 3, 4]
}
nodes = [i for i in graph_data.keys()]
patterns = []
for top, connect_tops in graph_data.items():
for connect_top in connect_tops:
patterns.append((top, connect_top))
G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(patterns)
nx.draw(G, with_labels=True)
plt.show()
グラフGの頂点集合V(G)を互いに素な部分集合V1, V2に分割し、V1の頂点同士、V2の頂点同士が隣接しないようにできるとき、Gを2部グラフと呼び、V1, V2を部集合と呼ぶ。部集合V1, V2を持つ2部グラフGにおいてV1の各頂点が、V2の全ての頂点と隣接しているとき、Gを完全2部グラフと呼ぶ。また、部集合の数をnとしたとき、n部グラフ、完全n部グラフが存在する。
2部グラフ
definition_src/bipartite_graph.py
A = {
1: [4, 5],
2: [5],
3: [6]
}
B = {
4: [1, 2],
5: [2],
6: [3]
}
A_nodes = [i for i in A.keys()]
B_nodes = [i for i in B.keys()]
nodes = A_nodes + B_nodes
patterns = []
for top, connect_tops in A.items():
for connect_top in connect_tops:
patterns.append((top, connect_top))
for top, connect_tops in B.items():
for connect_top in connect_tops:
patterns.append((top, connect_top))
G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(patterns)
nx.draw(G, with_labels=True)
plt.show()
完全2部グラフ
definition_src/complete_bipartite_graph.py
A = {
1: [4, 5, 6],
2: [4, 5, 6],
3: [4, 5, 6]
}
B = {
4: [1, 2, 3],
5: [1, 2, 3],
6: [1, 2, 3]
}
A_nodes = [i for i in A.keys()]
B_nodes = [i for i in B.keys()]
nodes = A_nodes + B_nodes
patterns = []
for top, connect_tops in A.items():
for connect_top in connect_tops:
patterns.append((top, connect_top))
G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(patterns)
nx.draw(G, with_labels=True)
plt.show()
頂点集合の最後のインデックスが、どの頂点とも隣接しないときのグラフを道グラフ、あるいは単に道という。
definition_src/path_graph.py
graph_data = {
1: [2],
2: [3],
3: [4],
4: []
}
nodes = [i for i in graph_data.keys()]
patterns = []
for top, connect_tops in graph_data.items():
for connect_top in connect_tops:
patterns.append((top, connect_top))
G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(patterns)
nx.draw(G, with_labels=True)
plt.show()
道グラフの最後のインデックスが最初のインデックスと隣接する時のグラフを閉路という。
definition_src/cycle.py
graph_data = {
1: [2],
2: [3],
3: [4],
4: [1]
}
nodes = [i for i in graph_data.keys()]
patterns = []
for top, connect_tops in graph_data.items():
for connect_top in connect_tops:
patterns.append((top, connect_top))
G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(patterns)
nx.draw(G, with_labels=True)
plt.show()
- 和集合
- 積集合
- 互いに素
- 完全グラフ
- クリーク
- 2部グラフ
- 部集合
- 完全2部グラフ
- n部グラフ
- 完全n部グラフ
- 道
- 閉路
グラフGの頂点vに接続している辺の本数を次数という。次数が偶数、あるいは奇数である頂点をそれぞれ偶点、奇点と呼ぶ。また、次数0の頂点を孤立点と呼ぶ。
- 次数
- 偶点
- 奇点
- 孤立点
有向グラフDの点vを始点としている弧の本数をvの出次数という。また、頂点vを終点としている弧の本数をvの入次数という。
- 出次数
- 入次数
全ての頂点の次数が同じrであるグラフを正則グラフ、あるいはr-正則グラフという
- 正則グラフ
隣接行列とは、列と行がグラフの頂点に対応したn次の正方行列のこと。
definition_src/adjacency_matrix.py
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
A = np.array([
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0]
])
tmp = nx.MultiGraph()
G = nx.from_numpy_matrix(A, parallel_edges=True, create_using=tmp)
nx.draw(G, with_labels=True)
plt.show()
グラフGの歩道とは、ある頂点から接続している辺と頂点を交互に通過していく道筋のこと。
歩道Wの始まりの頂点をWの始点、終わりの頂点をWの終点という。
また、Wに含まれている辺の本数nをWの長さという。始点と終点を歩道Wの端点という。
始点と終点が一致しているときは歩道は閉じているという。
同じ辺を含まない歩道を小道、同じ頂点を含まない歩道を道という。
閉じた小道を回路、閉じた道を閉路という。閉路は、その長さが偶数の時、偶閉路、奇数の時は奇閉路という。
- 隣接行列
- 歩道
- 始点
- 終点
- 長さ
- 端点
- 閉じている
- 小道
- 道
- 回路
- 閉路
- 偶閉路
- 奇閉路
有向グラフに関する有向小道、有向道、有向回路、有向閉路は、 それぞれグラフにおける小道、道、回路、閉路の各辺を同じ向きの弧に置き換えたものである。
- 有向小道
- 有向道
- 有向回路
- 有向閉路
ある頂点が連結グラフを分けることがあるとき、この頂点を切断点と呼ぶ。 切断点を繋ぐ辺のことを橋と呼ぶ。 切断点が集まった集合によって、連結グラフを分離するとき、この集合を切断集合という。 切断点は1頂点からなる切断集合である。
- 切断点
- 橋
- 切断集合
- 分離する
始点と終点が同じ2本の道P1とP2が内素であるとは、P1とP2が始点と終点以外に共有店を持たないことである。
- 内素
グラフGの2頂点u, vを結ぶ道の中で、最も長さの短い長さを、uとvの距離という。
連結グラフGに対して、uとvがそれぞれグラフの始点と終点であるときの距離を直径という。
- 距離
- 直径