The On-Line Encyclopedia of Bongard Problems

Search: concept:graph

Displaying 1-10 of 14 results found.

( next ) page 1 2

Sort: id Format: long Filter: (all | no meta | meta) Mode: (words | no words)

Each graph vertex is uniquely defined by its connections (the graph does not admit nontrivial automorphisms) vs. the graph admits nontrivial automorphisms.

(edit; present; nest [left/right]; search; history)

	CROSSREFS	`Adjacent-numbered pages: BP385 BP386 BP387 BP388 BP389 * BP391 BP392 BP393 BP394 BP395`
	KEYWORD	`precise, allsorted, notso, traditional, preciseworld`
	CONCEPT	`graph (info \| search),` `self-reference (info \| search),` `topological_transformation (info \| search),` `imagined_shape (info \| search),` `imagined_entity (info \| search)`
	WORLD	`connected_graph [smaller \| same \| bigger]`
	AUTHOR	`Jago Collins`

BP391

There exists an edge such that removing it yields two disconnected graphs (i.e., the minimum number of edges whose removal results in two disconnected graphs is 1) vs. the minimum number of edges whose removal results in two disconnected graphs is 2.

(edit; present; nest [left/right]; search; history)

	CROSSREFS	`Adjacent-numbered pages: BP386 BP387 BP388 BP389 BP390 * BP392 BP393 BP394 BP395 BP396`
	KEYWORD	`nice, precise, traditional, preciseworld`
	CONCEPT	`graph (info \| search),` `distinguishing_crossing_curves (info \| search),` `existence (info \| search),` `imagined_shape (info \| search),` `imagined_entity (info \| search)`
	WORLD	`connected_graph [smaller \| same \| bigger]`
	AUTHOR	`Jago Collins`

BP560

There exists a closed trail that hits each edge exactly once vs. not so.

(edit; present; nest [left/right]; search; history)

	COMMENTS	`Left examples are called "Eulerian graphs."` `A connected graph is Eulerian if and only if each vertex is incident to an even number of edges.`
	CROSSREFS	`Adjacent-numbered pages: BP555 BP556 BP557 BP558 BP559 * BP561 BP562 BP563 BP564 BP565`
	KEYWORD	`precise, allsorted, math, traditional, preciseworld`
	CONCEPT	`graph (info \| search),` `distinguishing_crossing_curves (info \| search),` `all (info \| search),` `even_odd (info \| search),` `existence (info \| search)`
	WORLD	`connected_graph [smaller \| same \| bigger]`
	AUTHOR	`Aaron David Fairbanks`

BP562

There exists a closed trail that hits each vertex exactly once vs. not so.

(edit; present; nest [left/right]; search; history)

	COMMENTS	`Left examples are called "Hamiltonian graphs."`
	CROSSREFS	`Adjacent-numbered pages: BP557 BP558 BP559 BP560 BP561 * BP563 BP564 BP565 BP566 BP567`
	KEYWORD	`math, traditional`
	CONCEPT	`graph (info \| search),` `distinguishing_crossing_curves (info \| search)`
	WORLD	`connected_graph [smaller \| same \| bigger]`
	AUTHOR	`Aaron David Fairbanks`

BP576

Vertices may be partitioned into two sets such that no two vertices in the same set are connected versus not so.

(edit; present; nest [left/right]; search; history)

	COMMENTS	`Left examples are called "bipartite graphs."`
	CROSSREFS	`Adjacent-numbered pages: BP571 BP572 BP573 BP574 BP575 * BP577 BP578 BP579 BP580 BP581`
	KEYWORD	`precise, allsorted, notso, math, traditional, preciseworld`
	CONCEPT	`graph (info \| search),` `distinguishing_crossing_curves (info \| search)`
	WORLD	`graph [smaller \| same \| bigger]`
	AUTHOR	`Aaron David Fairbanks`

BP788

Graph contains a "loop" a.k.a. cycle (cyclic) versus graph is acyclic.

(edit; present; nest [left/right]; search; history)

	CROSSREFS	`Adjacent-numbered pages: BP783 BP784 BP785 BP786 BP787 * BP789 BP790 BP791 BP792 BP793`
	KEYWORD	`nice, precise, allsorted, math, traditional, preciseworld`
	CONCEPT	`graph (info \| search),` `distinguishing_crossing_curves (info \| search),` `loop (info \| search)`
	WORLD	`connected_graph [smaller \| same \| bigger]`
	AUTHOR	`Aaron David Fairbanks`

BP905

Graph can be redrawn such that no edges intersect vs. not so.

(edit; present; nest [left/right]; search; history)

	COMMENTS	`A graph is a collection of vertices and edges. Vertices are the dots and edges are the lines that connect the dots. On the left, all edges can be redrawn (curved lines are allowed and moving vertices is allowed) such that no edges cross each other and each vertex is still connected to the same other vertices. These graphs are called planar.`
	CROSSREFS	`Adjacent-numbered pages: BP900 BP901 BP902 BP903 BP904 * BP906 BP907 BP908 BP909 BP910`
	KEYWORD	`nice, precise, allsorted, notso, math, left-null, preciseworld`
	CONCEPT	`graph (info \| search),` `topological_transformation (info \| search)`
	WORLD	`connected_graph [smaller \| same \| bigger]`
	AUTHOR	`Molly C Klenzak`

BP932

Every vertex is connected to every other vs. vertices are connected in a cycle (no other connections).

(edit; present; nest [left/right]; search; history)

	COMMENTS	`Complete graphs with zero, one, two, or three vertices would be ambiguously categorized (fit in overlap of both sides).` `Left examples are called "fully connected graphs." Right examples are called "cycle graphs."`
	CROSSREFS	`Adjacent-numbered pages: BP927 BP928 BP929 BP930 BP931 * BP933 BP934 BP935 BP936 BP937`
	KEYWORD	`precise, left-narrow, right-narrow, both, preciseworld`
	CONCEPT	`graph (info \| search),` `distinguishing_crossing_curves (info \| search),` `all (info \| search),` `loop (info \| search)`
	WORLD	`connected_graph [smaller \| same \| bigger]`
	AUTHOR	`Aaron David Fairbanks`

BP1016

Rigid vs. not rigid.

(edit; present; nest [left/right]; search; history)

	REFERENCE	`Henneberg, L. (1911), Die graphische Statik der starren Systeme, Leipzig` `Jackson, Bill. (2007). Notes on the Rigidity of Graphs.` `Laman, Gerard. (1970), "On graphs and the rigidity of plane skeletal structures", J. Engineering Mathematics, 4 (4): 331–340.` `Pollaczek‐Geiringer, Hilda (1927), "Über die Gliederung ebener Fachwerke", Zeitschrift für Angewandte Mathematik und Mechanik, 7 (1): 58–72.`
	CROSSREFS	`Adjacent-numbered pages: BP1011 BP1012 BP1013 BP1014 BP1015 * BP1017 BP1018 BP1019 BP1020 BP1021`
	KEYWORD	`nice, physics, help`
	CONCEPT	`rigidity (info \| search),` `graph (info \| search),` `imagined_motion (info \| search)`
	WORLD	`planar_connected_graph [smaller \| same \| bigger] zoom in left (rigid_planar_connected_graph)`
	AUTHOR	`Aaron David Fairbanks`

BP1099

Considering only the ways they are connected, anything that can be said about a given node can be said about every other node vs. not so.

(edit; present; nest [left/right]; search; history)

	REFERENCE	`https://en.wikipedia.org/wiki/Vertex-transitive_graph`
	CROSSREFS	`Adjacent-numbered pages: BP1094 BP1095 BP1096 BP1097 BP1098 * BP1100 BP1101 BP1102 BP1103 BP1104`
	KEYWORD	`precise, allsorted, notso, math, preciseworld`
	CONCEPT	`graph (info \| search),` `distinguishing_crossing_curves (info \| search)`
	WORLD	`graph [smaller \| same \| bigger] zoom in left`
	AUTHOR	`Leo Crabbe`

( next ) page 1 2

		Hints
(Greetings from The On-Line Encyclopedia of Bongard Problems!)