| 词条 | Clique graph |
| 释义 |
In graph theory, a clique graph of an undirected graph G is another graph K(G) that represents the structure of cliques in G. Clique graphs were discussed at least as early as 1968,[1] and a characterization of clique graphs was given in 1971.[2] Formal definitionA clique of a graph G is a set X of vertices of G with the property that every pair of distinct vertices in X are adjacent in G. A maximal clique of a graph G is a clique X of vertices of G, such that there is no clique Y of vertices of G that contains all of X and at least one other vertex. Given a graph G, its clique graph K(G) is a graph such that
The clique graph K(G) can also be characterized as the intersection graph of the maximal cliques of G.[3] CharacterizationA graph H is the clique graph K(G) of another graph if and only if there exists a collection C of cliques in H whose union covers all the edges of H, such that C forms a Helly family. This means that, if S is a subset of C with the property that every two members of S have a non-empty intersection, then S itself should also have a non-empty intersection. However, the cliques in C do not necessarily have to be maximal cliques.[2] When H =K(G), a family C of this type may be constructed in which each clique in C corresponds to a vertex v in G, and consists of the cliques in G that contain v. These cliques all have v in their intersection, so they form a clique in H. The family C constructed in this way has the Helly property, because any subfamily of C with pairwise nonempty intersections must correspond to a clique in G, which can be extended to a maximal clique that belongs to the intersection of the subfamily.[2] Conversely, when H has a Helly family C of its cliques, covering all edges of H, then it is the clique graph K(G) for a graph G whose vertices are the disjoint union of the vertices of H and the elements of C. This graph G has an edge for each pair of cliques in C with nonempty intersection, and for each pair of a vertex of H and a clique in C that contains it. However, it does not contain any edges connecting pairs of vertices in H. The maximal cliques in this graph G each consist of one vertex of H together with all the cliques in C that contain it, and their intersection graph is isomorphic to H.[2] However, this characterization does not lead to efficient algorithms: the problem of recognizing whether a given graph is a clique graph is NP-complete.[4] References1. ^{{cite journal|last=Hamelink|first=Ronald C.|title=A partial characterization of clique graphs|journal=Journal of Combinatorial Theory|volume=5|pages=192–197|year=1968|doi=10.1016/S0021-9800(68)80055-9}} 2. ^1 2 3 {{cite journal|last1=Roberts|first1=Fred S.|author1-link=Fred S. Roberts|last2=Spencer|first2=Joel H.|author2-link=Joel Spencer|title=A characterization of clique graphs|journal=Journal of Combinatorial Theory | series = Series B|volume=10|pages=102–108|year=1971|doi=10.1016/0095-8956(71)90070-0}} 3. ^{{cite journal|last1=Szwarcfiter|first1=Jayme L.|author1-link=Jayme Luiz Szwarcfiter|last2=Bornstein|first2=Claudson F.|title=Clique graphs of chordal and path graphs|journal=SIAM Journal on Discrete Mathematics|volume=7|pages=331–336|year=1994|doi=10.1137/S0895480191223191|citeseerx=10.1.1.52.521}} 4. ^{{cite journal | last1 = Alcón | first1 = Liliana | last2 = Faria | first2 = Luerbio | last3 = de Figueiredo | first3 = Celina M. H. | last4 = Gutierrez | first4 = Marisa | doi = 10.1016/j.tcs.2009.01.018 | issue = 21-23 | journal = Theoretical Computer Science | mr = 2519298 | pages = 2072–2083 | title = The complexity of clique graph recognition | volume = 410 | year = 2009}} External links
1 : Graph operations |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。