無向辺と有向辺を同じように表したい
from 2026/06/10
無向辺と有向辺を同じように表したい
Summer498.icon
数学の変数に代入する時にオーバーロードする方法を思いついた
$ x=1\ {\rm and}\ 2とすると、
$ x=1が真かつ$ x=2が真になる
$ x=3とかは偽になる
何がしたいのか：グラフ理論の無向グラフを有向グラフと同じ型で表したい
有向グラフ$ G=(V,E)
$ a,b\in V,\ e=(a,b)\in E\sube V\times V
無向グラフ$ G=V,E
$ a,b\in V,\ e=(a,b)\ {\rm and}\ (b,a)\in E\sube V\times V
よく見る無向グラフの定義は
無向グラフ$ G=V,E
$ a,b\in V,\ e=\{a,b\}\in E\sube 2^V
部分集合を使うのはインターフェイスの大きさが冗長
$ |2^V|もある
実質的には$ |V\times V|でいいのに
あ。部分集合はハイパーグラフで使える
$ e=\{a,b\}と$ e=\{a,b,c\}と$ e=\{a,b,c,d\}を持つグラフとか作れる
ほな$ E\sube2^Vか～ミルクボーイ.icon
当初の適用対象のつもりのものが無くなった
あーっと、更に前提が違うわ。グラフを定義する時は辺に直接代入せずに関数を噛ませるんだ。その方が色々柔軟になる。
$ G=(V,E,\mu)
有向グラフ：$ \mu:E\to V\times V
無向グラフ：$ \mu:E\to2^V
これだとタプルと集合の取り扱いの話になる
$ (a,b)と$ \{a,b\}
$ a\in\{a,b\}に相当する$ a\in(a,b)を表せるように$ \inを定義しておけば大体同じように取り扱えるはず