連續區間圖與螺旋多邊形的警衛問題

Abstract

一無向圖 G 是區間圖的充分必要條件是 : G 的 maximal cliques 能被 排成一個次序 ，使得對於 G 中的每一頂點 v 而言 ，包含 v 的 maximal cliques 是連續的 。在這篇論文中 ，我們將介紹一些相交圖 ，它們是區間圖的子集合 ，我們稱之為連續區間圖 。我們將証明 ， 一 無向區間圖 G 是連續區間圖的充分必要條件是 : G 是連通圖而且不僅 G 的 maximal cliques 能被排成一個次序 ，使得對於 G 中的每一頂點 v 而言 ，包含 v 的 maximal cliques 是連續的 ， 而且 G 的頂點也能 被排成一個次序 ，使得對於 G 中的每一 maximal clique A 而言 ，包 含於 A 中的頂點也是連續的 。連續區間圖有許多好的性質 ，而且可以 用來解決螺旋多邊形的警衛問題 。 An undirected graph G is an interval graph if and only if the maximal cliques of G can be linearly ordered such that, for every vertex v of G, the maximal cliques containing v occur consecutively. In this thesis, we shall introduce a class of intersection graphs, which is a subset of interval graphs; we call them consecutive interval graphs. We shall prove that an undirected graph G is consecutive interval graph if and only if G is connected and not only the maximal cliques of G can be linearly ordered such that, for every vertex v of G, the maximal cliques containing v occur consecutively but also the vertices of G can be linearly ordered such that, for every maximal clique A of G, the vertices contained in A occur consecutively. Consecutive interval graphs have many interesting properties and can be used to solve the guard problem in spiral polygons.