REPOZYTORIUM UNIWERSYTETU
W BIAŁYMSTOKU
UwB

Proszę używać tego identyfikatora do cytowań lub wstaw link do tej pozycji: http://hdl.handle.net/11320/7621
Tytuł: About Supergraphs. Part I
Autorzy: Koch, Sebastian
Słowa kluczowe: supergraph
graph operations
Data wydania: 2018
Data dodania: 4-mar-2019
Wydawca: DeGruyter Open
Źródło: Formalized Mathematics, Volume 26, Issue 2, Pages 101-124
Abstrakt: Drawing a finite graph is usually done by a finite sequence of the following three operations. 1. Draw a vertex of the graph. 2. Draw an edge between two vertices of the graph. 3. Draw an edge starting from a vertex of the graph and immediately draw a vertex at the other end of it.By this procedure any finite graph can be constructed. This property of graphs is so obvious that the author of this article has yet to find a reference where it is mentioned explicitly. In introductionary books (like [10], [5], [9]) as well as in advanced ones (like [4]), after the initial definition of graphs the examples are usually given by graphical representations rather than explicit set theoretic descriptions, assuming a mutual understanding how the representation is to be translated into a description fitting the definition. However, Mizar [2], [3] does not possess this innate ability of humans to translate pictures into graphs. Therefore, if one wants to create graphs in Mizar without directly providing a set theoretic description (i.e. using the createGraph functor), a rigorous approach to the constructing operations is required.In this paper supergraphs are defined as an inverse mode to subgraphs as given in [8]. The three graph construction operations are defined as modes extending Supergraph similar to how the various remove operations were introduced as submodes of Subgraph in [8]. Many theorems are proven that describe how graph properties are transferred to special supergraphs. In particular, to prove that disconnected graphs cannot become connected by adding an edge between two vertices that lie in the same component, the theory of replacing a part of a walk with another walk is introduced in the preliminaries.
Afiliacja: Johannes Gutenberg University, Mainz, Germany
URI: http://hdl.handle.net/11320/7621
DOI: 10.2478/forma-2018-0009
ISSN: 1426-2630
e-ISSN: 1898-9934
metadata.dc.identifier.orcid: 0000-0002-9628-177X
Typ Dokumentu: Article
Występuje w kolekcji(ach):Formalized Mathematics, 2018, Volume 26, Issue 2

Pliki w tej pozycji:
Plik Opis RozmiarFormat 
forma_2018_26_2_002.pdf268,7 kBAdobe PDFOtwórz
Pokaż pełny widok rekordu Zobacz statystyki


Pozycja ta dostępna jest na podstawie licencji Licencja Creative Commons CCL Creative Commons