In graph theory, the line graph L(G) of a graph G is a graph such that A diagram of a graph with 6 vertices and 7 edges. ...
each node of L(G) represents an edge of G; and
any two nodes of L(G) are adjacent if and only if their corresponding edges are incident, meaning they share a common endnode, in G.
A line graph L(G) can easily be constructed from any graph by
creating a node in L(G) for each edge of G, and
for each node in L(G), adding an edge to all of its neighbors (all the other nodes corresponding to edges in G that touch the node at either end of the edge in G).
Some graphs are not line graphs. For example, the graph
is not a line graph of any other graph. The line graph of the above graph is Image File history File links Download high resolution version (790x793, 28 KB) Summary An example of a graph that is not a line graph. ...
Another Example Image File history File links Download high resolution version (597x832, 32 KB) Summary The line graph of Image:LineGraphExampleA.png. ...
Graph G
Line Graph L(G)
To get to the Line Graph L(G) from the Graph G place a vertex on the middle of each edge on Graph G then join up the vertices that are placed on edges that join in a vertex on graph G, once you have done that remove that bits that are part of the original Graph and you have Line Graph L(G) Image File history File links Line_graph_construction_(original). ... Image File history File links Line_graph_construction_(original). ... Image File history File links Line_graph_construction_(result). ... Image File history File links Line_graph_construction_(result). ...
Thus, properties of edges in graphs can be translated into properties about vertices in linegraphs; for instance, the size of a maximum independent set in a linegraph is the same as the size of a maximum matching in the original graph.
The linegraph of a connected graph is connected.
The edge chromatic number of a graph is equal to the vertex chromatic number of its linegraph.
Matrix graphs also produce displays containing multiple component graphs; however, each of those component graphs are (or can be) based on the same set of cases and the graphs are generated for all combinations of variables from one or two lists.
This graph is useful in exploratory data analysis to determine the extent of missing (and/or "out of range") data and whether the patterns of those data occur randomly.
In a categorized ternary plot, one component graph is produced for each level of the grouping variable (or user-defined subset of data) and all the component graphs are arranged in one display to allow for comparisons between the subsets of data (categories).
Feeds |
Contact