To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Intersection graph

From Wikipedia, the free encyclopedia

An example of how intersecting sets define a graph.

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.

YouTube Encyclopedic

  • 1/3
    Views:
    2 597
    280 558
    6 156
  • Intersection Graph | Lesson 3
  • Finding The Point of Intersection of Two Linear Equations With & Without Graphing
  • Intersection of two graph | Operations on graph | Graph theory | Discrete Mathematics

Transcription

Formal definition

Formally, an intersection graph G is an undirected graph formed from a family of sets

by creating one vertex vi for each set Si, and connecting two vertices vi and vj by an edge whenever the corresponding two sets have a nonempty intersection, that is,

All graphs are intersection graphs

Any undirected graph G may be represented as an intersection graph. For each vertex vi of G, form a set Si consisting of the edges incident to vi; then two such sets have a nonempty intersection if and only if the corresponding vertices share an edge. Therefore, G is the intersection graph of the sets Si.

Erdős, Goodman & Pósa (1966) provide a construction that is more efficient, in the sense that it requires a smaller total number of elements in all of the sets Si combined. For it, the total number of set elements is at most n2/4, where n is the number of vertices in the graph. They credit the observation that all graphs are intersection graphs to Szpilrajn-Marczewski (1945), but say to see also Čulík (1964). The intersection number of a graph is the minimum total number of elements in any intersection representation of the graph.

Classes of intersection graphs

Many important graph families can be described as intersection graphs of more restricted types of set families, for instance sets derived from some kind of geometric configuration:

Scheinerman (1985) characterized the intersection classes of graphs, families of finite graphs that can be described as the intersection graphs of sets drawn from a given family of sets. It is necessary and sufficient that the family have the following properties:

  • Every induced subgraph of a graph in the family must also be in the family.
  • Every graph formed from a graph in the family by replacing a vertex by a clique must also belong to the family.
  • There exists an infinite sequence of graphs in the family, each of which is an induced subgraph of the next graph in the sequence, with the property that every graph in the family is an induced subgraph of a graph in the sequence.

If the intersection graph representations have the additional requirement that different vertices must be represented by different sets, then the clique expansion property can be omitted.

Related concepts

An order-theoretic analog to the intersection graphs are the inclusion orders. In the same way that an intersection representation of a graph labels every vertex with a set so that vertices are adjacent if and only if their sets have nonempty intersection, so an inclusion representation f of a poset labels every element with a set so that for any x and y in the poset, x ≤ y if and only if f(x) ⊆ f(y).

See also

References

  • Čulík, K. (1964), "Applications of graph theory to mathematical logic and linguistics", Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Prague: Publ. House Czechoslovak Acad. Sci., pp. 13–20, MR 0176940.
  • Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966), "The representation of a graph by set intersections" (PDF), Canadian Journal of Mathematics, 18 (1): 106–112, doi:10.4153/CJM-1966-014-3, MR 0186575, S2CID 646660.
  • Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.
  • McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, vol. 2, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3, MR 1672910.
  • Szpilrajn-Marczewski, E. (1945), "Sur deux propriétés des classes d'ensembles", Fund. Math., 33: 303–307, doi:10.4064/fm-33-1-303-307, MR 0015448.
  • Schaefer, Marcus (2010), "Complexity of some geometric and topological problems" (PDF), Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. 334–344, doi:10.1007/978-3-642-11805-0_32, ISBN 978-3-642-11804-3.
  • Scheinerman, Edward R. (1985), "Characterizing intersection classes of graphs", Discrete Mathematics, 55 (2): 185–193, doi:10.1016/0012-365X(85)90047-0, MR 0798535.

Further reading

  • For an overview of both the theory of intersection graphs and important special classes of intersection graphs, see McKee & McMorris (1999).

External links

This page was last edited on 9 February 2024, at 23:24
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.