Regular graphIn graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree k is called a k‐regular graph or regular graph of degree k. Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.
Graph labelingIn the mathematical discipline of graph theory, a graph labelling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph. Formally, given a graph G = (V, E), a vertex labelling is a function of V to a set of labels; a graph with such a function defined is called a vertex-labeled graph. Likewise, an edge labelling is a function of E to a set of labels. In this case, the graph is called an edge-labeled graph. When the edge labels are members of an ordered set (e.
Component (graph theory)In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices.
Edge coloringIn graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors.
Chordal graphIn the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree.
Rainbow matchingIn the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Given an edge-colored graph G = (V,E), a rainbow matching M in G is a set of pairwise non-adjacent edges, that is, no two edges share a common vertex, such that all the edges in the set have distinct colors. A maximum rainbow matching is a rainbow matching that contains the largest possible number of edges. Rainbow matchings are of particular interest given their connection to transversals of Latin squares.
Minimum spanning treeA minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.
Robot combatRobot combat is a mode of robot competition in which custom-built machines fight using various methods to incapacitate each other. The machines have generally been remote-controlled vehicles rather than autonomous robots. Robot combat competitions have been made into television series, including Robot Wars in the UK and BattleBots in the US. These shows were originally broadcast in the late 1990s to early 2000s and experienced revivals in the mid-2010s.
Domestic robotA domestic robot is a type of service robot, an autonomous robot that is primarily used for household chores, but may also be used for education, entertainment or therapy. While most domestic robots are simplistic, some are connected to Wi-Fi home networks or smart environments and are autonomous to a high degree. There were an estimated 16.3 million service robots in 2018. People began to design robots for processing materials and construct products, especially during the Industrial Revolution in the period about 1760 to around 1840.
Medial graphIn the mathematical discipline of graph theory, the medial graph of plane graph G is another graph M(G) that represents the adjacencies between edges in the faces of G. Medial graphs were introduced in 1922 by Ernst Steinitz to study combinatorial properties of convex polyhedra, although the inverse construction was already used by Peter Tait in 1877 in his foundational study of knots and links. Given a connected plane graph G, its medial graph M(G) has a vertex for each edge of G and an edge between two vertices for each face of G in which their corresponding edges occur consecutively.
