Indifference graph (nonfiction): Difference between revisions
Jump to navigation
Jump to search
(Created page with "thumb|An indifference graph, formed from a set of points on the real line by connecting pairs of points whose distance is at most one.In graph...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
[[File:Indifference_graph.png|thumb|An indifference graph, formed from a set of points on the real line by connecting pairs of points whose distance is at most one.]]In | [[File:Indifference_graph.png|thumb|An indifference graph, formed from a set of points on the real line by connecting pairs of points whose distance is at most one.]]In [[Graph theory (nonfiction)|graph theory]], an '''indifference graph''' is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. | ||
Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals (intervals none of which contains any other one). Based on these two types of interval representations, these graphs are also called '''unit interval graphs''' or '''proper interval graphs'''; they form a subclass of the interval graphs. | Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals (intervals none of which contains any other one). Based on these two types of interval representations, these graphs are also called '''unit interval graphs''' or '''proper interval graphs'''; they form a subclass of the interval graphs. | ||
| Line 6: | Line 6: | ||
<gallery> | <gallery> | ||
File:Forbidden indifference subgraphs.png|link=Forbidden graph characterization (nonfiction)|[[Forbidden graph characterization (nonfiction)|Forbidden graph characterization]] says it "is forbidden to discuss indifference graphs." | |||
</gallery> | </gallery> | ||
== Fiction cross-reference == | == Fiction cross-reference == | ||
* [[Gnomon algorithm]] | |||
* [[Mathematics]] | |||
== Nonfiction cross-reference == | == Nonfiction cross-reference == | ||
* [[Forbidden graph characterization (nonfiction)]] | * [[Forbidden graph characterization (nonfiction)]] | ||
* [[Graph theory (nonfiction)]] | |||
* [[Mathematics (nonfiction)]] | * [[Mathematics (nonfiction)]] | ||
| Line 21: | Line 26: | ||
[[Category:Nonfiction (nonfiction)]] | [[Category:Nonfiction (nonfiction)]] | ||
[[Category:Graph theory (nonfiction)]] | |||
[[Category:Mathematics (nonfiction)]] | [[Category:Mathematics (nonfiction)]] | ||
Latest revision as of 18:46, 8 December 2017
In graph theory, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other.
Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals (intervals none of which contains any other one). Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.
In the News
Forbidden graph characterization says it "is forbidden to discuss indifference graphs."
Fiction cross-reference
Nonfiction cross-reference
External links:
- Indifference graph @ Wikipedia