monochromatic graph
Смотреть что такое "monochromatic graph" в других словарях:
Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia
Monochromatic electromagnetic plane wave — In general relativity, the monochromatic electromagnetic plane wave spacetime is the analog of the monochromatic plane waves known from Maxwell s theory. The precise definition of the solution is a bit complicated, but very instructive. Any exact … Wikipedia
Monochromatic triangle — The monochromatic triangle problem is a decision problem that is known to be NP complete. Input: An n node undirected graph G(V,E) with node set V and edge set E. Question: Can the edges, E, of G be partitioned into two disjoint sets E1 and E2,… … Wikipedia
Degeneracy (graph theory) — In graph theory, a k degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph s edges. The degeneracy of a graph is the smallest… … Wikipedia
Hadwiger conjecture (graph theory) — In graph theory, the Hadwiger conjecture (or Hadwiger s conjecture) states that, if an undirected graph G requires k or more colors in any vertex coloring, then one can find k disjoint connected subgraphs of G such that each subgraph is connected … Wikipedia
Ramsey's theorem — This article goes into technical details quite quickly. For a slightly gentler introduction see Ramsey theory. In combinatorics, Ramsey s theorem states that in any colouring of the edges of a sufficiently large complete graph (that is, a simple… … Wikipedia
Probabilistic method — This article is not about probabilistic algorithms, which give the right answer with high probability but not with certainty, nor about Monte Carlo methods, which are simulations relying on pseudo randomness. The probabilistic method is a… … Wikipedia
Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… … Wikipedia
Sim (pencil game) — The game of Sim is played by two players, Red and Blue, on a board consisting of six dots ( vertices ). Each dot is connected to each other with a line.Two players take turns coloring any uncolored lines. One player colors in red, and the other… … Wikipedia
optics — /op tiks/, n. (used with a sing. v.) the branch of physical science that deals with the properties and phenomena of both visible and invisible light and with vision. [1605 15; < ML optica < Gk optiká, n. use of neut. pl. of OPTIKÓS; see OPTIC,… … Universalium
List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… … Wikipedia
