Internet & Web Application

Problems in Graph Theory

สำรวจประเด็นปัญหาในงานวิจัยเรื่อง Graph Theory เพื่อให้ทราบถึง Key Word เพื่อสามารถค้นคว้าต่อได้

Enumeration

การค้นหา Graph ที่ตรงกับคุณสมบัติที่กำหนด (ตอนนี้ ไม่เข้าใจว่า หา Subgraph หรือ Generate ขึ้นมาใหม่ ?!?) ซึ่งอ้างอิงตาม Wiki บอกว่า “Find how many non-isomorphic graphs have a given property.”

“ถ้าเรามี Graph : G เราจะสามารถหา Graph : H ใดใด ที่มีคุณสมบัติตรงตาม Euler Circuit ได้กี่รูปแบบ ? .. อะไรบ้าง ?” ===> คือปัญหา Graph Enumeration ใช่หรือไม่ ?

Subgraphs, induced subgraphs, and minors

A common problem, called the subgraph isomorphism problem, is finding a fixed graph as a subgraph in a given graph. [Fixed graph คืออะไร ?]
One reason to be interested in such a question is that many graph properties are hereditary [กรรมพันธุ์ , ส่งต่อ] for subgraphs, which means that a graph has the property if and only if all subgraphs have it too.
Unfortunately, finding maximal subgraphs of a certain kind is often an NP-complete problem.

A similar problem is finding induced subgraphs in a given graph. Again, some important graph properties are hereditary with respect to induced subgraphs, which means that a graph has a property if and only if all induced subgraphs also have it. [จะมีคุณสมบัติ ต่อเมื่อ Subgraph มีคุณสมบัติดังกล่าว]
Finding maximal induced subgraphs of a certain kind is also often NP-complete. For example,

Still another such problem, the minor containment problem, is to find a fixed graph as a minor of a given graph. [สร้าง Graph จาก Subgraph ?]
A minor or subcontraction of a graph is any graph obtained by taking a subgraph and contracting some (or no) edges. Many graph properties are hereditary for minors, which means that a graph has a property if and only if all minors have it too. A famous example:

Another class of problems has to do with the extent to which various species and generalizations of graphs are determined by their point-deleted subgraphs, for example:

Graph Coloring

เช่นใช้สีให้น้อยที่สุด สำหรับระบายพื้นที่ ของประเทศที่อยู่ติดกัน โดยไม่ซ้ำกัน เป็นต้น

Many problems have to do with various ways of coloring graphs, for example:

Route Problems

Network Flow

There are numerous problems arising especially from applications that have to do with various notions of flows in networks, for example:

Visibility Graph Problems

Covering Problems

Covering problems are specific instances of subgraph-finding problems, and they tend to be closely related to the clique problem or the independent set problem.

Applications

Network Analysis, Computer Network, Transportation Network, Social Network, Chemistry & Physic

อ้างอิงจาก

Advertisements
มาตรฐาน

ใส่ความเห็น

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

WordPress.com Logo

You are commenting using your WordPress.com 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