Degree

Regular Graph / Factor

無向圖當中,「Regular Graph」是每一點都連著一樣多的邊的圖;「Factor」是每一點都連著一樣多的邊的子圖。

簡而言之:每個點的度數都一樣的圖、子圖。

我們可以在名稱開頭冠上數字、橫槓,明確呈現度數。例如1-Regular Graph是每個點都連著一條邊的圖,2-Factor是每個點都連著兩條邊的子圖。

Complete Graph / Clique

無向圖當中,「完全圖Complete Graph」是所有兩點之間都有一條邊的圖;「團Clique」是所有兩點之間都有一條邊的子圖。

簡而言之:每個點的度數都是V-1的圖、子圖。

Degree

無向圖當中,一個點的「度Degree」,就是碰觸鄰邊的次數。沒有自環的情況下,「度Degree」等於鄰邊數量。

有向圖當中,可以進一步細分為「入度In-degree」與「出度Out-degree」,分別是指入邊的數目、出邊的數目。

「度」可以呈現一個點與其他點的聯繫強度。

有向圖當中,因為每條邊都是有始有終,所以整張圖的入度總數目必等於出度總數目。

無向圖當中,以邊為主角,每條邊碰到兩個點。所有碰到的點的度數加起來,就是邊數的兩倍。換句話說,整張圖的度數總和必等於邊數的兩倍。

UVa 12035

給定各點degree求原圖(Erdos-Gallai Theorem)

http://mathworld.wolfram.com/GraphicSequence.html

小遊戲:http://armorgames.com/play/5900/king-of-bridges

小遊戲:http://www.agame.com/game/connectors.html

求得其中一種可能性,時間複雜度O(V²)。

UVa 10720 11414

給定各點degree求原圖(Havel-Hakimi Algorithm)

度數按照大到小排序
d₁ d₂ d₃ ... is graphical
iff d₂-1 d₃-1 ... dd₁+1-1 dd₁+2 dd₁+3 dd₁+4 ... is graphical
    |-------- d₁ -------|

求得其中一種可能性,時間複雜度O(V²)。

Oriented Graph

一張無向圖,無向邊改成有向邊,稱做「定向圖」。替每一條邊選擇一個方向,稱作「定向Orientation」。

根據Robbins' theorem,沒有橋的無向圖,一定能改成強連通的Orientation,反之亦然。

UVa 610 10972

Moore Graph

https://en.wikipedia.org/wiki/Moore_graph

Width(Under Construction!)

Width

http://mathsci.kaist.ac.kr/~jisujeong/jisu_grow2015.pdf
http://link.springer.com/article/10.1007/s00453-015-0033-7

Tree Decomposition

http://www.cs.uu.nl/docs/vakken/an/an-treewidth.pdf
http://www.mi.fu-berlin.de/en/inf/groups/abi/teaching/lectures_past/WS0910/V____Discrete_Mathematics_for_Bioinformatics__P1/material/scripts/treedecomposition1.pdf
http://web.engr.illinois.edu/~jeffe/teaching/comptop/2009/notes/treewidth.pdf
一、樹分解的點,是原圖的點集合。
二、圖上的邊的兩端點,位於樹分解的同一點。
三、圖上的點,位於樹分解的某棵連通子樹的每一點。
四、樹分解最小的點,大小減一,就是寬度。

Partial k-Tree

https://code.google.com/codejam/contest/801485/dashboard#s=a&a=1

UVa 12615

Clique Tree

ICPC 7458

Tree Root

http://www.csie.ntu.edu.tw/~hil/paper/swat06.ppt

Isomorphism(Under Construction!)

Graph Isomorphism

http://en.wikipedia.org/wiki/Graph_canonization
http://en.wikipedia.org/wiki/Graph_isomorphism
http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
http://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem
http://en.wikipedia.org/wiki/Graph_sandwich_problem

Graph Enumeration

http://en.wikipedia.org/wiki/Graph_enumeration

Tree Isomorphism

http://www.cs.upc.edu/~valiente/graph-00-01-c.pdf
use radix sort O(nd) = O(#son + #grandson) = O(n + n) = O(n)

http://en.wikipedia.org/wiki/Graph_isomorphism_problem#Solved_special_cases

subtree isomorphism問題可以用DP+matching來解決
https://code.google.com/codejam/contest/dashboard?c=32005#s=a&a=3
http://www.lsi.upc.edu/~valiente/riga-tre.pdf
為什麼對?
https://github.com/juanplopes/icpc/blob/master/uva/12489.cpp

UVa 10729 10904 12489 ICPC 2935

Tree Enumeration

http://mathworld.wolfram.com/LabeledTree.html
http://en.wikipedia.org/wiki/Prüfer_sequence
http://www.matrix67.com/blog/archives/682

Prüfer Code:把一棵樹轉換成獨特的編號。

UVa 10843

Tree Distance(Tree Similarity)

兩棵樹的距離:

Edit Distance
Rotation Distance
Chain Rotation Distance