Internet & Web Application

เรื่องของ Graph Theory #1 : Overview (Wiki)

ทำ Thesis ที่ Algorithm ต้องสัมผัสกับเรื่อง Graph Theory แต่ไม่ชำนาญเลย .. ก็กระไรอยู่

Graph ประกอบไปด้วย Node (หรือ Vertex) กับ Edge (ทั้งแบบมีทิศทาง – ทำให้ได้ Directed Graph เชื่อมระหว่าง Ordered pair จาก Node หนึ่ง ไปยัง Node ถัดไป .. กับแบบไม่มีทิศทาง – Undirected Graph เชื่อมระหว่าง Pair ของ Node)

  • Paper เกี่ยวกับ Graph ฉบับแรกพบในปี 1736 โดย Euler พูดถึงปัญหา Seven Bridges of Königsberg ที่ต้องหาวิธีข้ามสะพานแต่ละอัน, ได้เพียงครั้งเดียว, ให้ครบทุกสะพาน, เพื่อไปยังเมืองต่างๆ และกลับมาจุดเริ่มต้นให้ได้
  • ปัญหา Graph enumeration is a subject of graph theory that deals with the problems of the following type: find how many non-isomorphic graphs have a given property.
  • ปัญหา four color problem: “Is it true that any map drawn in the plane may have its regions colored with four colors, in such a way that any two regions having a common border have different colors?”.

Graph Category

ลองดู เรื่องของ Graph Theory #2 : Graph Category

Data Structure of Storaged Graph

เก็บ Graph บน Computer นิยมใช้ทั้งแบบ Link List และ Matrix , โดยสังเกตจากความสัมพันธ์ของ Vertex/Vertex = Adjacency หรือ Vertex/Edge = Incidence

Incidence List :

The edges are represented by an array containing pairs (ordered if directed) of vertices (that the edge connects) and possibly weight and other data. Vertices connected by an edge are said to be adjacent.

เช่น e1 = [ a , c ] , e2 = [ a , b ] , e3 = [ b , c ]

Adjacency List :

Much like the incidence list, each vertex has a list of which vertices it is adjacent to. This causes redundancy in an undirected graph: for example, if vertices A and B are adjacent, A’s adjacency list contains B, while B’s list contains A. Adjacency queries are faster, at the cost of extra storage space.

สามารถเก็บในรูปแบบ Link List ของ Vertex ที่ Adjacent (เป็น Neighbor) กัน เช่น a := b -> c -> e -> null

Adjacency List จะได้ในเรื่องของความเร็วในการค้นหาว่า Vertex ใดอยู่ติดกันบ้าง

Adjacency Matrix :

This is the n by n matrix A, where n is the number of vertices in the graph. If there is an edge from some vertex x to some vertex y, then the element a x,y is 1 (or in general the number of xy edges), otherwise it is 0.

Matrix ที่ Row & Col เป็น Node & Node ที่เชื่อมต่อกัน .. matrix member แทน edge weight

Adjacency Matirx จะมีประสิทธิภาพในการหา Subgraph และ Reverse Directed Graph

Incidence Matrix :

The graph is represented by a matrix of size |V| (number of vertices) by |E| (number of edges) where the entry [vertex, edge] contains the edge’s endpoint data (simplest case: 1 – connected, 0 – not connected).

Laplacian matrix or Kirchhoff matrix or Admittance matrix
This is defined as DA, where D is the diagonal degree matrix. It explicitly contains both adjacency information and degree information.
Distance matrix
A symmetric n by n matrix D whose element d x,y is the length of a shortest path between x and y; if there is no such path d x,y = infinity. It can be derived from powers of A: d_{x,y}=\min\{n\mid A^n[x,y]\ne 0\}.

Problem in Graph

ย้ายไป Problems in Graph Theory


  • wiki


Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s