Skip to content

Instantly share code, notes, and snippets.

@matonix
Created October 10, 2019 02:17
Show Gist options
  • Save matonix/b15c65896dd212bf0a159e9ee346b334 to your computer and use it in GitHub Desktop.
Save matonix/b15c65896dd212bf0a159e9ee346b334 to your computer and use it in GitHub Desktop.
Labelled-edges についての質問に答えたので自分用にメモ.

linguini Yesterday at 8:36 PM algebraic-graphsのData.Graph.LabelledのGraphにOverlayがなくてConnect zeroで代用してるのってなんでなんですか (edited)

matonix 1 hour ago 度々すみません,2018年にLabelled-edgesに関して発表されているようです(今見てます…) https://skillsmatter.com/skillscasts/12361-labelled-algebraic-graphs#showModal?modal-signup-complete

Labelled-edges

  • Graph a を Graph e a に拡張(e はラベル)

  • Connect に モノイドな e パラメータが追加され,Overlay = Connect zero と定義

  • 辺が存在しないことを表す場合,label を zero にする(加法単位元)

    • 外から意味付けを加える場合は適宜変換してあげる(e.g. label zero は∞の距離を表す,とか)
  • モノイド e 同士の演算を行う <+> 演算子はラベルの意味に従って与える

    • e.g. 距離なら <+> は min
  • ラベルの列の合成 <.> (a-b, b-cなる辺があるなら,a-cのラベルは何か?)

    • e.g. 距離なら+ (加算)
    • 結合律を満たす
  • 空のラベルの列は label one で表す(乗法単位元)

    • e.g. 距離なら label one は 0
  • e はSemiringになる

  • labelled graph から unlabelled graph を作るには,Bool-labelled にする

    • e=Bool, 0=False, 1=True, <+>=(||), <.>=(&&)

動画を見ました.私なりの質問への答えは以下になります.

辺ラベルを持つグラフをくっつけるとき,「辺の重複をどのように解決するか」,「連続する2つ以上の辺のラベルをどのように解釈するか(例えば,重み付きグラフの場合は辺の重みからパスの重みを算出する需要があったりします)」といった問題への対処が必要になります.

Andrey氏は,ラベルをSemiringと見なすことで,複数の需要(辺を容量とみなしたり,距離とみなしたり)を満たそうとしています.このとき,Semiringにおける零元を持つ辺は「辺がない」ことを表しているようです.

Overlayは2つのグラフを単に重ねる操作ですが,辺が重複する場合のことが(Unlabelledでは)考えられていません.そこで,辺が重複する場合はSemiringになっているラベルの加法を適用するというアイディアを採用しているようです.例えば,距離の重みがついたグラフでは,距離が短い方を採用したりできます.

Connect e は2つのグラフ間の全部の辺にラベル e を付与する操作(ちょっと自信ないです…)ですが,Connect zero とすることで,2つのグラフの辺の間に「辺を張らない」ことを表現できます.

以上が私の理解でした…どなたか補足していただけると幸いです.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment