研究動機

完全有向グラフにおける重み付き 競争グラフ

斎藤研究室４年 栗山慶史

研究動機

グラフ理論を使って離散数学の中だけで研究 するのではなく、社会の問題について研究

してみたい

現実の社会の状態を考える

研究動機

グラフ理論 頂点の集合 と辺集合で

構成されるグラフの性質について 研究する学問

社会の状態 人 の集合と人の繋がりの集合 で構成されるネットワークについて

研究する学問

頂点、辺 人、人の繋がり

研究動機

グラフ理論において頂点一つ一つの大きさ を気にしない

現実の社会では、人は一人一人違う

頂点の差別化を図る

競争グラフ

競争グラフとは、有向グラフで、どの頂点が競争関係 になっているのかを表しているグラフ

重み付き競争グラフ

競争グラフに対して、頂点に[0,1]の実数を割 り振って、足して１以上になった頂点対のみ辺 で結んだもの

0.4

0.6 0.5

0.7 0.2

0.8

0.4+0.2=0.6 <1.0

0.4+0.6=1.0

0.6+0.5=1.1 0.4+0.5=0.9

=>1.0

=>1.0

<1.0

重み付き競争グラフ

重み付き競争グラフを特徴付けたい

有向グラフが完全有向グラフの時に特徴付け が得られた

誘導部分グラフ

誘導部分グラフと部分グラフの違い

誘導部分グラフに 取りたい

OK NG

研究結果 1

定理：

グラフGが完全有向グラフの重み付き競争グラ フであるための必要十分条件は

Ｇが のいずれも誘導部分

グラフに含まない連結グラフことである

証明 ( 必要条件 )

Gが のいずれかを誘導部 分グラフ に含むと仮定する

a1

a2

a3

a4

a1+a2>=1 --- ① a3+a4>=1 --- ② a1+a3< 1 --- ③ a2+a4< 1 --- ④ a1+a4< 1 --- ⑤ a2+a3< 1 --- ⑥

①

②

a1+a2+a3+a4>=2

③

④

a1+a2+a3+a4< 2 矛盾

証明 ( 必要条件 )

a1+a2>=1 --- ① a2+a4>=1 --- ② a3+a4>=1 --- ③

a1

a2

a3

a4 a1

a2

a3

a4

a1+a3< 1 --- ④ a1+a4< 1 --- ⑤ a2+a3< 1 --- ⑥

①

③

a1+a2+a3+a4>=2

⑤

⑥

a1+a2+a3+a4< 2 矛盾 a1+a2>=1 --- ①

a1+a3>=1 --- ② a2+a4>=1 --- ③ a3+a4>=1 --- ④ a1+a4< 1 --- ⑤ a2+a3< 1 --- ⑥

①

④

⑤

⑥

証明 ( 必要条件 )

Gが のいずれかを誘導部 分グラフに含むと仮定する

a1

a2

a3

a4

a1+a2>=1 --- ① a3+a4>=1 --- ② a1+a3< 1 --- ③ a2+a4< 1 --- ④ a1+a4< 1 --- ⑤ a2+a3< 1 --- ⑥

①

②

a1+a2+a3+a4>=2

③

④

a1+a2+a3+a4< 2 矛盾

仮定が

間違い 証明された

証明 ( 十分条件 )

次に、Ｇが を 誘導部分

グラフに含まない連結グラフとする Ｇの最大次数の頂点をｘとする

ｘは全ての頂点と繋がっていることを示す

証明 ( 十分条件 )

ｘと繋がっていない点があると仮定する

xの近傍

（n点) x

・・・・・・・・・・・・・・

矛盾

・・・・・・・

n-1 + 1 + 1 = n+1 > n = xの次数 矛盾

仮定が

間違い

証明 ( 十分条件 )

次に、Ｇが を 誘導部分

グラフに含まない連結グラフとする Ｇの最大次数の頂点をｘとする

ｘは全ての頂点と繋がっていることを示す 証明できた

証明 ( 十分条件 )

G

x G-x

C¹ C² C^r

・・・・・・・・・

但し、 |C1|>= |C2|>=・・・>= |Cr|

|C2|= 1を示す

誘導部分グラフ が導かれてしまう

|C3|>= |C4|>=・・・・・・>= |Cr|=1

証明 ( 十分条件 )

C¹

を誘導部分グラフ にもたない

数学的帰 納法

[0,1]

C² C³ C^r

・・・・・・・・・

0 0 0

1 x

QED

研究結果 2

定理：

完全有向グラフの重み付き競争グラフの補グラ フも完全有向グラフの重み付き競争グラフであ る

証明

もし、補グラフに が誘導部分 グラフに含むと仮定する

その補グラフである元のグラフには

矛盾

QED

今後の課題

• 一般の有向グラフの重み付き競争グラフに 対しての特徴づけをしてみたい

• 社会の複雑な対象をモデル化、分析できるよ うな定理を提案したい