グラフ理論 - star

グラフ理論

完全グラフ

位数の定理

多重グラフ

$ \sum_{v\in V(G)}d_G(v)=2|E(G)|

閉路グラフ

よこいちのグラフ

出次数

定理と証明を言え

入次数

正則グラフの定義を言え

誘導部分グラフの定義を言え

最大次数

握手の補題

位数

同型

オイラーグラフ

ハミルトングラフ

フラーリのアルゴリズム

オイラー回路

回路

郵便配達員閉歩道

グラフ$ G

頂点$ V(G) or 点$ E(G)と呼ばれる元の集合

有限グラフ

V and Eが有限

位数$ |V(G)|

頂点の数

サイズ$ |E(G)|

辺の数

uとvが隣接する

https://gyazo.com/dbabb19de7370967185ee9ff48b9204d

このときのeはu, vと接続するという

u, vは端点という

近傍

$ vの近傍$ N_G(v):

ある頂点に隣接する頂点全体の集合

https://gyazo.com/ba140512063ae5d7144ceccd60cc4c84

位数6

サイズ3

隣接:

v1とv3

v1とv2

v5とv6

非隣接:

v1とv4, v5, v6

v2とv3, v4, v5, v6

v3とv2, v4, v5, v6

v4とv1, v2, v3, v5, v6

v5とv1, v2, v3, v4

v6とv1, v2, v3, v4

近傍:

$ N(v_1)=\set{v_3, v_2}

$ N(v_2)=\set{v_1}

$ N(v_3)=\set{v_1}

$ N(v_4)=\varnothing

$ N(v_5)=\set{v_6}

$ N(v_6)=\set{v_5}

多重グラフ

以下の2つを許したグラフ

多重辺

https://gyazo.com/d895057ff4fca82cbbdb44d7be48a37c

ループ

https://gyazo.com/676bd1b7e4e33b247946bcb0cce037ba

単純グラフ

2つを許さないグラフ

有向グラフ（ダイグラフ）$ D

弧

始点

周転

対称弧

https://gyazo.com/3d308ac4cffe9baf926baf7f3c9e73dc

多重弧

https://gyazo.com/50c4800247470ee70c27974178f673b6

部分グラフ$ H\subseteq G:

$ (V(H)\subseteq V(G))\land (E(H)\subseteq E(G))となるグラフ

全域部分グラフ

部分グラフの等号成立時に全域部分グラフと呼ばれる

誘導部分グラフ$ \lang S\rang:

$ S\sube V(G)となる$ Sを頂点集合とする$ Gの極大なグラフ

極大なグラフ：

$ Sを頂点集合とするすべての$ Gの部分グラフが$ \lang S\rangの部分グラフとなる

https://gyazo.com/26276b0445042e4de17939d170910428

https://gyazo.com/04201950cbc2a5a4805a6ae8c36cba15

https://gyazo.com/b9ad243366658b7bfa0204ca4a4d0e13https://gyazo.com/d88b52df2ebb77b63432b7510885afa7

グラフ理論においてエッジが左のようになる状態は考えない

$ Gと$ Hが同型:

$ f（全単射）:V(G)\rightarrow V(H)

$ \exists f\text{s.t.}\forall u,v\in V(G),\set{u, v}\in E(G)\iff\set{f(u),f(v)}\in E(H)

まとめ方がふめいだし定義もムズイが見た目でだいたいわかるだろう

道

歩道

閉路

木

林

この辺のネーミングどうなの？

定義

日本語で書くのがめんどい

ずをいっぱい描くか？