21 |
A note on quasi-robust cycle basesOstermeier, Philipp-Jens, Hellmuth, Marc, Klemm, Konstantin, Leydold, Josef, Stadler, Peter F. January 2009 (has links) (PDF)
We investigate here some aspects of cycle bases of undirected graphs that allow the iterative construction of all elementary cycles. We introduce the concept of quasi-robust bases as a generalization of the notion of robust bases and demonstrate that a certain class of bases of the complete bipartite graphs K m,n with m,n _> 5 is quasi-robust but not robust. We furthermore disprove a conjecture for cycle bases of Cartesian product graphs.
|
22 |
Prostředí Rodokmen v matematice na 1. st. ZŠ / Environment of Family-tree in primary school mathematicsBartošová, Zuzana January 2011 (has links)
The Rodokmen (Family tree) environment is one of the many envirnments listed in Fraus publishing house textbooks based on the RVP pro ZV (The Framework Educatinal Programme for Basic Education). The environment offers a tool for building of the mathematical schema of terms and their inter-realations as well as the development of the logical thought. In the theorethicl part of this Diploma thesis the relationship of the Rodokmen environment to the RVP pro ZV is being explained, basic mathematical and geneaologic terminology is stated. In this part of the thesis I also explain the relations in the set cocncept, clasify the family relationships and adress the methodology of the age example solving. In the practical part of the thesis I - by the way of experiment - determine how and in what context students understand the stated mathematical terms, the way they apply the understanding in order to solv the relation and age exams or problems, where the numeric operations take place.
|
23 |
Ensino e aprendizagem de problemas de produto cartesiano: inter-relações entre diferentes representaçõesSilva, Vera Lucia da 16 November 2006 (has links)
Made available in DSpace on 2016-04-27T16:57:50Z (GMT). No. of bitstreams: 1
EDM - Vera Lucia da Silva.pdf: 1384460 bytes, checksum: 3234ebd8c11c96412594a6df13e184cf (MD5)
Previous issue date: 2006-11-16 / Secretaria da Educação do Estado de São Paulo / This research is about a teaching project aiming at mastering abilities and
concepts related to the solution of problems of Cartesian product.
The selected population were students of 4th Grade from a State School in
the eastern region of the city of São Paulo.
Our reference is the G. Vergnaud Conceptual Fields Theory and we took in
consideration theoretical elements from researchers interested in studying the
multiplicative reasoning.
Data were collected from continuous observation and evaluation of the
students performance, from the analyses of the materials produced by them and
from interviews.
The activities were designed with the intent of establishing connections
between adding and multiplying processes and the processes involved in the
determination of all the pairs of the Cartesian product.
These connections become evident when represented by means of spatial
relations promoting the evolution of non-conventional representations, produced
by the students, to conventional representations, in Cartesian graphics and tree
diagrams.
The major contributions of this research for understanding the cognitive
operations involved in solving Cartesian product problems are the repertory of
non-conventional processes, employed by the selected group of participants, and
their justification, and the analyses of the phenomena that occur in the passage
from one to the other of the different representations of the Cartesian product.
This research also offers contribution for the training of elementary
education teachers / Nesta pesquisa, desenvolvemos uma proposta de ensino voltada ao
domínio de competências e conceitos, relativos à resolução de problemas de
multiplicação cartesiana.
A população selecionada foi constituída por alunos de uma classe de 4a
série do Ensino Fundamental, de uma Escola Estadual localizada da zona leste
do Estado de São Paulo.
Tomamos como referência a Teoria dos Campos Conceituais, de G.
Vergnaud, e consideramos elementos teóricos de pesquisadores que
desenvolvem pesquisas sobre o pensamento multiplicativo.
Os dados foram obtidos por meio de registro e avaliação contínua do
comportamento dos alunos no desenvolvimento das atividades, da análise do
material produzido por eles e de entrevistas, entre outros.
No desenvolvimento das atividades, buscamos estabelecer conexões entre
procedimentos aditivos e multiplicativos e os processos envolvidos na
determinação de todos os pares do produto cartesiano.
Essas conexões foram ressaltadas ao serem representadas por meio de
relações espaciais, promovendo a evolução de representações não
convencionais, produzidas pelos alunos, para representações convencionais, em
gráficos cartesianos e de árvore .
Como principais contribuições desta pesquisa para a compreensão das
operações cognitivas envolvidas na resolução de problemas de produto
cartesiano, ressalte-se: o levantamento de um repertório de procedimentos não
convencionais empregados pela classe selecionada e suas justificativas, a análise
de fenômenos ocorridos na passagem de uma para outra das diferentes
representações do produto cartesiano.
A pesquisa oferece, igualmente, contribuições para a formação de
professores do ensino fundamental
|
24 |
Códigos identificadores em algumas classes de grafos / Identifying codes in some classes of graphsFélix, Juliana Paula 19 February 2018 (has links)
Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-16T10:48:35Z
No. of bitstreams: 2
Dissertação - Juliana Paula Félix - 2018.pdf: 1739140 bytes, checksum: 14e7528cefac5d3322e49131936f3c86 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-16T10:49:04Z (GMT) No. of bitstreams: 2
Dissertação - Juliana Paula Félix - 2018.pdf: 1739140 bytes, checksum: 14e7528cefac5d3322e49131936f3c86 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-03-16T10:49:04Z (GMT). No. of bitstreams: 2
Dissertação - Juliana Paula Félix - 2018.pdf: 1739140 bytes, checksum: 14e7528cefac5d3322e49131936f3c86 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2018-02-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work, we investigate the problem of finding identifying codes of minimum size in a variety
of graph classes, such as trees corona products, Cartesian products and complementary prisms. For
caterpillar trees, we show the minimum size of an identifying code on complete caterpillars,
brooms and double brooms. We also prove a sharp upper bound for the general case. For coronas
$K_n \circ \overline{K}_m$, we prove what is the minimum size of an identifying code. We
demonstrate a sharp upper bound for an identifying code of the Cartesian product of a star and a
path $K_{1,n} \square P_m$ and, when $n=3$, we conjecture that the limit proposed is minimum.
We also find the minimum cardinality of an identifying code in the complementary prism of
complete bipartite graphs and complete split graphs, among with other results: we demonstrate that
the complementary prism graph $G\overline{G}$ is identifiable if, and only if, $G$ has at least
two vertices; we find what is the smallest size possible of an identifying code of complementary
prisms; we prove a sharp upper bound for an identifying code of the complementary prism
$G\overline{G}$ of a connected graph $G$, showing that the set $C = V(G)$ is an identifying
code with the size proposed and, finally, we determine the size of a minimum identifying code of
the complementary prism of a complete bipartite graph, showing that it is an example of a graph
that attains our upper bound. / Neste trabalho, investigamos o problema de se encontrar códigos identificadores de cardinalidade
mínima em diversas classes de grafos, tais como árvores, produtos coronas, produtos Cartesianos e
prismas complementares. Para árvores caterpillar, determinamos a cardinalidade mínima de um
código identificador em caterpillars completo, grafos broom e broom duplo, e provamos um limite
superior justo para caterpillars gerais. Para coronas, determinamos a cardinalidade mínima de um
código identificador em $K_n \circ \overline{K}_m$. Para produtos Cartesianos, investigamos
códigos identificadores em grafos $K_{1,n} \square P_m$, definimos um limite superior justo para
o caso em que $n=3$ e um limite superior mais abrangente para o caso em que $n \geq 3$. Quando
$n=3$, conjecturamos que o limite proposto é mínimo. Para prismas complementares de grafos,
encontramos o tamanho de um código identificador mínimo em grafos bipartidos completos e
grafos split completos. Para prismas complementares, obtivemos ainda outros resultados:
demonstramos que um grafo prisma complementar $G\overline{G}$ é identificável se, e somente
se, a ordem de $G$ é pelo menos dois; definimos o menor tamanho possível de um código
identificador em um grafo $G\overline{G}$; determinamos um limite superior justo para o código
identificador de um grafo conexo, mostrando também que seu conjunto de vértices é um conjunto
identificador com o tamanho proposto e, finalmente, mostramos que o grafo bipartido completo é
um exemplo de grafo que atinge a igualdade do limite superior apresentado.
|
25 |
Colouring, circular list colouring and adapted game colouring of graphsYang, Chung-Ying 27 July 2010 (has links)
This thesis discusses colouring, circular list colouring and adapted game colouring of graphs. For colouring, this thesis obtains a sufficient condition for a planar graph to be 3-colourable. Suppose G is a planar graph. Let H_G be the graph with vertex set V (H_G) = {C : C is a cycle of G with |C| ∈ {4, 6, 7}} and edge set E(H_G) = {CiCj : Ci and Cj have edges in common}. We prove that if any 3-cycles and 5-cycles are not adjacent to i-cycles for 3 ≤ i ≤ 7, and H_G is a forest, then G is 3-colourable.
For circular consecutive choosability, this thesis obtains a basic relation among chcc(G), X(G) and Xc(G) for any finite graph G. We show that for any
finite graph G, X(G) − 1 ≤ chcc(G) < 2 Xc(G). We also determine the value of chcc(G) for complete graphs, trees, cycles, balanced complete bipartite graphs and some complete multi-partite graphs. Upper and lower bounds for chcc(G) are given for some other classes of graphs.
For adapted game chromatic number, this thesis studies the adapted game chromatic number of various classes of graphs. We prove that the maximum
adapted game chromatic number of trees is 3; the maximum adapted game chromatic number of outerplanar graphs is 5; the maximum adapted game
chromatic number of partial k-trees is between k + 2 and 2k + 1; and the
maximum adapted game chromatic number of planar graphs is between 6 and 11. We also give upper bounds for the Cartesian product of special classes of graphs, such as the Cartesian product of partial k-trees and outerplanar graphs, or planar graphs.
|
26 |
O número de Carathéodory na convexidade geodésica de grafos / The Carathéodory number in the geodesic convexity of graphsLira, Eduardo Silva 01 December 2016 (has links)
Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2017-01-02T14:12:29Z
No. of bitstreams: 2
Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-01-03T09:39:46Z (GMT) No. of bitstreams: 2
Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-01-03T09:39:46Z (GMT). No. of bitstreams: 2
Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2016-12-01 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / From Carathéodory’s theorem arises the definition of the Carathéodory number for graphs. This number is well-known for monophonic and triangle-path convexities. It is limited for some classes of graphs on P3 and geodesic convexities but is known to be unlimited only on P3-convexity. Driven by open questions in geodesic convexity, in this work we study the Carathéodory number in this convexity. For general graphs and cartesian product, we prove that the Carathéodory number is unlimited. We characterize the Carathéodory number for trees, cographs, for the complementary prisms of cographs and simple graphs Kn, Pn and Cn, for the complement and the complementary prism of the graph KnKn and for the cartesian products PnxPm, KnxKm and PnxKm. / Do Teorema de Carathéodory da geometria surge a definição do número de Carathéodory para grafos. Este número é bem determinado na convexidade monofônica e na convexidade de caminho de triângulos. Ele é limitado para algumas classes de grafos nas convexidades P3 e geodésica, mas só foi provado ser ilimitado na convexidade P3. Motivados pelas questões em aberto na convexidade geodosésica, neste trabalho estudamos o número de Carathéodory nesta convexidade. Para grafos gerais e para produtos cartesianos, provamos que o número de Carathéodory é ilimitado. Determinamos o número de Carathéodory para árvores, cografos, para o prisma complementar de cografos e dos grafos simples Kn, Pn e Cn, para o complemento e prisma complementar do grafo KnKn e para os produtos cartesianos PnxPm, KnxKm e PnxKm.
|
27 |
Proper connection number of graphsDoan, Trung Duy 16 August 2018 (has links)
The concept of \emph{proper connection number} of graphs is an extension of proper colouring and is motivated by rainbow connection number of graphs. Let $G$ be an edge-coloured graph. Andrews et al.\cite{Andrews2016} and, independently, Borozan et al.\cite{Borozan2012} introduced the concept of proper connection number as follows: A coloured path $P$ in an edge-coloured graph $G$ is called a \emph{properly coloured path} or more simple \emph{proper path} if two any consecutive edges receive different colours. An edge-coloured graph $G$ is called a \emph{properly connected graph} if every pair of vertices is connected by a proper path. The \emph{proper connection number}, denoted by $pc(G)$, of a connected graph $G$ is the smallest number of colours that are needed in order to make $G$ properly connected. Let $k\geq2$ be an integer. If every two vertices of an edge-coloured graph $G$ are connected by at least $k$ proper paths, then $G$ is said to be a \emph{properly $k$-connected graph}. The \emph{proper $k$-connection number} $pc_k(G)$, introduced by Borozan et al. \cite{Borozan2012}, is the smallest number of colours that are needed in order to make $G$ a properly $k$-connected graph.
The aims of this dissertation are to study the proper connection number and the proper 2-connection number of several classes of connected graphs. All the main results are contained in Chapter 4, Chapter 5 and Chapter 6.
Since every 2-connected graph has proper connection number at most 3 by Borozan et al. \cite{Borozan2012} and the proper connection number of a connected graph $G$ equals 1 if and only if $G$ is a complete graph by the authors in \cite{Andrews2016, Borozan2012}, our motivation is to characterize 2-connected graphs which have proper connection number 2. First of all, we disprove Conjecture 3 in \cite{Borozan2012} by constructing classes of 2-connected graphs with minimum degree $\delta(G)\geq3$ that have proper connection number 3. Furthermore, we study sufficient conditions in terms of the ratio between the minimum degree and the order of a 2-connected graph $G$ implying that $G$ has proper connection number 2. These results are presented in Chapter 4 of the dissertation.
In Chapter 5, we study proper connection number at most 2 of connected graphs in the terms of connectivity and forbidden induced subgraphs $S_{i,j,k}$, where $i,j,k$ are three integers and $0\leq i\leq j\leq k$ (where $S_{i,j,k}$ is the graph consisting of three paths with $i,j$ and $k$ edges having an end-vertex in common).
Recently, there are not so many results on the proper $k$-connection number $pc_k(G)$, where $k\geq2$ is an integer. Hence, in Chapter 6, we consider the proper 2-connection number of several classes of connected graphs. We prove a new upper bound for $pc_2(G)$ and determine several classes of connected graphs satisfying $pc_2(G)=2$. Among these are all graphs satisfying the Chv\'tal and Erd\'{o}s condition ($\alpha({G})\leq\kappa(G)$ with two exceptions). We also study the relationship between proper 2-connection number $pc_2(G)$ and proper connection number $pc(G)$ of the Cartesian product of two nontrivial connected graphs.
In the last chapter of the dissertation, we propose some open problems of the proper connection number and the proper 2-connection number.
|
Page generated in 0.0776 seconds