split graph
Смотреть что такое "split graph" в других словарях:
Split graph — In graph theory, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer in two papers in 1977, and independently introduced by Tyshkevich and… … Wikipedia
Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia
Graph toughness — In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t tough if, for every k > 1, G cannot be split into k different connected components by the removal of fewer than tk vertices. For instance, a graph… … Wikipedia
Graph of desire — The graph of desire is a conceptual tool from the psychoanalytic theory of Jacques Lacan.HistoryLacan devised numerous quasi mathematical diagrams to represent the structure of the unconscious and its points of contact with empirical and mental… … Wikipedia
Threshold graph — In graph theory, a threshold graph is a graph that can be constructed from a one vertex graph by repeated applications of the following two operations: #Addition of a single isolated vertex to the graph #Addition of a single dominating vertex to… … Wikipedia
Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue … Wikipedia
Metric dimension (graph theory) — In graph theory, the metric dimension of a graph G is the minimum number of vertices in a subset S of G such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP … Wikipedia
Book (graph theory) — In graph theory, a book (usually written B p) is a split graph consisting of p triangles sharing a common edge (known as the base of the book). Given a graph G, one often writes bk(G) for the largest book contained within G. Note: in the past,… … Wikipedia
Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… … Wikipedia
Chordal graph — A cycle (black) with two chords (green). As for this part, the graph is chordal. However, removing one green edge would result in a non chordal graph. Indeed, the other green edge with three black edges would form a cycle of length four with no… … Wikipedia
Distance-hereditary graph — A distance hereditary graph. In graph theoretic mathematics, a distance hereditary graph (also called a completely separable graph)[1] is a graph in which the distances in any connected induced subgraph are the same as they are in the original… … Wikipedia
