Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Complete bipartite graph
Summary
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.
Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher. Llull himself had made similar drawings of complete graphs three centuries earlier.
A complete bipartite graph is a graph whose vertices can be partitioned into two subsets V_1 and V_2 such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a bipartite graph (V_1, V_2, E) such that for every two vertices v_1 ∈ V_1 and v_2 ∈ V_2, v_1v_2 is an edge in E. A complete bipartite graph with partitions of size = m and = n, is denoted K_m,n; every two graphs with the same notation are isomorphic.
For any k, K_1,k is called a star. All complete bipartite graphs which are trees are stars.
The graph K_1,3 is called a claw, and is used to define the claw-free graphs.
The graph K_3,3 is called the utility graph. This usage comes from a standard mathematical puzzle in which three utilities must each be connected to three buildings; it is impossible to solve without crossings due to the nonplanarity of K_3,3.
The maximal bicliques found as subgraphs of the digraph of a relation are called concepts. When a lattice is formed by taking meets and joins of these subgraphs, the relation has an Induced concept lattice. This type of analysis of relations is called formal concept analysis.
Given a bipartite graph, testing whether it contains a complete bipartite subgraph K_i,i for a parameter i is an NP-complete problem.
A planar graph cannot contain K_3,3 as a minor; an outerplanar graph cannot contain K_3,2 as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (9)
CS-450: Algorithms II
A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper
MATH-360: Graph theory
The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc
MATH-448: Statistical analysis of network data
A first course in statistical network analysis and applications.
Related lectures (32)
Graphical models: Inference and Factor Graphs
Explores graphical models, factor graphs, and probabilistic inferences in complex systems.
Matroids: Matroid Intersection
Covers the concept of matroids, focusing on matroid intersection and the properties of subsets of a ground set.
Markov Chains and Applications
Explores Markov chains, Ising Model, Metropolis algorithm, and Glauber dynamics.
Related publications (74)
Related people (25)
Related units (3)
Related concepts (36)
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with n vertices is called C_n. The number of vertices in C_n equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it. There are many synonyms for "cycle graph".
Dense graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements. Due to this, the way that density is defined often depends on the context of the problem.
Edge coloring
In 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.