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