グラフ理論入門 ６ ラベル付きグラフ
６ ラベル付きグラフ
6.1 魔法グラフと優美な木
- マジック(magic, super-magicとも)
- q辺のグラフにおいて、その各辺を1,2,...,qの値でラベル付けしたとき、各頂点に接続する辺のラベルの総和がすべて同じにできるとき、そのグラフをマジックと呼ぶ。
- 反マジック(antimagic)
- q辺のグラフにおいて、その各辺を1,2,...qの値でラベル付けしたとき、各頂点に接続する辺のラベルの総和がすべて異なるようにできるとき、そのグラフを反マジックと呼ぶ。
- 優美(graceful)
- n頂点の木は、n-1辺を持つ。今、頂点に1,2,...nとラベル付けし、各辺に1,2,...n-1とラベル付けするときに、各辺のラベルの値が、その辺の端頂点のラベルの値の差にできるとき、その木を優美であるという。
- Ringerはすべての木は優美であると予想し、また、かなりのクラスの木について、それは証明されたが、木、一般についてはまだ証明されていない。
6.2 保守的グラフ
- 有向グラフ(directed graph, D)
- 弧(arcs)
- 向きを指定された辺のこと。
- 弧集合(arc-set)
- 弧の全体の集合のこと。
- 保守的(conservative)
- 無向グラフのマジックに相当する概念である。
- 辺に向きを指定し、かつ1,2,...,qとラベル付けしたときに、各頂点に入ってくる弧のラベルの総和と、出て行く弧のラベルの総和とが等しくできるようなとき、保守的であるという。
- キルヒホッフの流率(Kirchhoff's Current Law)
- 保守的なグラフの向き付けとラベル付けにおいて、各頂点では、入ってくるラベルの総和は出て行くラベルの総和に等しい。
- 簡単のため、「各頂点での有向和(directed sum)は０である」と言う。
- 強意で保守的(strongly conservative)
- q辺を持つグラフGがあり、どんな数hに対しても、Gの辺の向きの指定と数h+1,h+2,...,h+qによるラベル付けが存在して、各頂点においてキルヒホッフの流率が成り立つとき、グラフGを強意で保守的と言う。
- 思いつきメモ
