4
$\begingroup$

In investigating an earlier question I proposed to this site, I came across a bipartite graph with certain properties. I briefly searched for other bipartite graph questions but didn't find anything similar.

Consider a graph $G=(V,E)$ such that it's vertices can be partitioned into subsets $\{U_1,\dotsc,U_n\}$ where for any edge $(a,b) \in E$ we have that if $a \in U_k$ then $b \in U_{k+1}$. Under this condition any adjacent pair of vertex subsets $U_k$ and $U_{k+1}$ (for $1 \leq k<n$) induce a bipartite subgraph. Additionally, $G$ can be depicted as a single bipartite graph by grouping the vertices $\{U_1, U_3, \dotsc\}$ and $\{U_2, U_4, \dotsc\}$ into the two separate parts.

Does this particular type of graph have a name, or any practical application or special properties? If so, has it been studied to any extent?

$\endgroup$
4
$\begingroup$

This type of graph is commonly called an Artificial Neural Network (usually just referred to by the acronym ANN). Artificial neural networks are a hot topic right now in the fields of computer science and engineering. See the buzzwords "machine learning" and "deep learning". Technically the term ANN refers to the entire data structure, but because of their ubiquity the term ANN is often used to refer to the underlying graph object too. Sometimes in papers you see it called a multilayer graph instead (a special case of a multipartite graph).

Artificial Neural Network
Image sourced from extremetech.com

For more information, see the tag wiki for , and also see Adam Harley's beautiful online visualization of a neural network.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.