Atividade 1 - Estrutura de Dados 2

Prévia do material em texto

Universidade Federal de Rondônia
Departamento de Ciências da Computação
Estrutura de Dados II – Lista 1 – Grafos
Giullia de Souza Santos
Thauan Costa da Silva
REVISÃO DE CONCEITOS
1. O que é ordem de um grafo?
R: Número de vértices que determinado grafo possui.
2. O que é um multigrafo?
R: Define-se como um grafo que possui pelo menos um vértice que se interliga mais
de uma vez a um outro mesmo vértice, ou seja esse vértice possui arestas
paralelas/múltiplas.
3. O que é um hipergrafo?
R: hipergrafo pode ser entendido como um grafo que possui pelo menos uma
interação em que uma aresta pode se conectar com mais de um outro vértice.
4. O que são vértices adjacentes?
R: Dois vértices são adjacentes quando são ligados pela mesma aresta (“vértices
vizinhos”).
5. O que são arestas adjacentes?
R: Duas arestas são adjacentes quando compartilham do mesmo vértice. Ou seja, elas
possuem um vértice/extremidade em comum.
6. O que é um grafo completo?
R: Um grafo é dito completo quando cada vértice do grafo possui uma relação de
adjacência com outro vértice, ou seja, todos seus vértices são adjacentes. Dada pela
função, um grafo K corresponde a arestas.𝑛(𝑛 − 1)/2
fonte: Wikipédia Grafo completo – Wikipédia, a enciclopédia livre
https://pt.wikipedia.org/wiki/Grafo_completo
7. O que é grau de um vértice?
R: O grau de um vértice é definido pelo número de ligações que faz, ou seja o número
de vezes que as arestas incidem sobre um vértice.
8. Em grafos orientados, o que é grau de saída? O que é grau de entrada de um vértice?
R: Grau de Saída: É o número de arestas que saem do vértice (arestas divergentes)
Grau de entrada: É o número de arestas que entram no vértice (arestas convergentes).
9. O que é sumidouro ou sorvedouro?
R: É um vértice com grau de saída nulo.
10. O que é fonte?
R: É um vértice com grau de entrada nulo.
11. O que é um grafo regular?
R: Um grafo é regular quando todos os seus vértices possuem o mesmo grau.
12. O que é um caminho entre dois vértices?
R: Pode ser definido como uma sequência de vértices e arestas que interligam dois
determinados vértices.
13. O que é o comprimento do caminho?
R: Em um grafo não valorado/ponderado é o número de arestas entre um caminho de
dois vértices.
14. O que é um caminho simples?
R: Um caminho é simples quando na sequência de arestas e vértices não há repetição
de vértice durante o caminho. Ou seja, todo o caminho de um vértice x a um vértice y,
todos os vértices ao longo do trajeto são distintos.
15. O que é um circuito?
R: Um circuito em um grafo é definido por um caminho que se inicia e termina no
mesmo vértice.
16. O que é um ciclo?
R: Um ciclo é um caminho que se inicia e termina no mesmo vértice (circuito), mas
com a condição de que todos os vértices entre esse caminho sejam distintos.
17. Quando um grafo é cíclico?
R: Um grafo é cíclico quando há pelo menos um caminho definido como ciclo no
grafo.
Exemplo: V1, V2, V3 E V1.
Fonte: Slides disponibilizados pela professora Carolina Watanabe
18. O que é um caminho hamiltoniano?
R: É um um caminho que percorre todos os vértices do grafo exatamente uma vez.
Exemplo no grafo ao lado, um caminho hamiltoniano:
E, A, B, C e D.
Fonte:Hamiltonian Graph in Discrete mathematics - javatpoint
19. O que é um grafo hamiltoniano?
R: É um grafo que contém um ciclo Hamiltoniano, ou seja é um grafo que pode ser
percorrido começando e terminando no mesmo vértice de forma que percorra todos
os vértices intermediários exatamente uma vez.
Exemplo: A, B, C, E, D e A.
Fonte:Hamiltonian Graph in Discrete mathematics - javatpoint
20. O que é um caminho euleriano?
R: É um caminho que percorre todas as arestas do grafo exatamente uma vez.
Exemplo no grafo ao lado um caminho euleriano:
B, C, D, B, A e D.
Fonte: Euler Graph in Discrete Mathematics - javatpoint
21. O que é um grafo euleriano?
R: É um grafo que contém um ciclo Euleriano, ou seja é um grafo que pode ser
percorrido começando e terminando no mesmo vértice de forma que percorra todas as
arestas exatamente uma vez.
Exemplo de grafo euleriano:
A, C, E, D, C, B e A
Fonte: Euler Graph in Discrete Mathematics - javatpoint
https://www.javatpoint.com/hamiltonian-graph-in-discrete-mathematics
https://www.javatpoint.com/hamiltonian-graph-in-discrete-mathematics
https://www.javatpoint.com/euler-graph-in-discrete-mathematics
https://www.javatpoint.com/euler-graph-in-discrete-mathematics
22. O que é um grafo conexo? Qual é a quantidade mínima de arestas para um grafo ser
conexo?
R: Um grafo é conexo quando todos os seus pares de vértices estão conectados por
uma aresta, caso contrário é considerado um grafo desconexo.
A quantidade mínima de arestas de um grafo conexo é definida pelo número de
vértices que o compõem, sendo um grafo de vértices, então para atender a condição𝑛
deverá ter arestas.𝑛 − 1 
Fonte: Slides disponibilizados pela professora Carolina Watanabe
23. O que é um grafo totalmente desconexo?
R: Um grafo é totalmente desconexo quando todos os seus vértices não estão
conectados por arestas.
24. É verdadeira a afirmação: Todo grafo euleriano é conexo. Todos os seus vértices
possuem grau par. Mostre um exemplo e um contra-exemplo.
R: A afirmação “Todo grafo euleriano é conexo” é verdadeira, pois pela definição um
grafo é euleriano quando contém um ciclo que percorre cada aresta do grafo
exatamente uma vez, portanto, necessariamente todos os seus vértices estão
conectados para completar o ciclo chamado de ciclo euleriano. Isso implica que todos
os seus vértices serão de grau par, isso ocorre porque para que exista esse ciclo é
necessário que cada aresta que entra no vértice também saia para o próximo, assim
sempre terá um número par de arestas incidentes sobre os vértices de um grafo
euleriano.
Exemplos de Grafos conexos, sendo um euleriano e o outro não euleriano:
Fonte: Slides disponibilizados pela professora Carolina Watanabe
25. O que é um dígrafo fortemente conexo?
R: É dito que um dígrafo é fortemente conexo quando em todos os seus vértices é
possível fazer um caminho direcionado de um vértice A até um vértice B e de B até
A. Sendo assim, há um caminho de ida e volta para cada par de vértices de todo o
dígrafo.
26. O que é um grafo bipartido?
R: Um grafo é dado como bipartido quando é possível particionar os vértices em dois
conjuntos/grupos independentes. Em que os vértices de um mesmo grupo não são
conectados por uma aresta.
Fonte: Graph Theory Types of Graphs - javatpoint
27. O que é uma árvore?
R: Uma árvore é um tipo de grafo conexo que não possui ciclos.
28. O que é uma floresta?
R: Uma floresta é um conjunto de árvores disjuntas.
29. O que é um subgrafo?
R: Um subgrafo é uma parte de um grafo maior, ou seja, um subgrafo é uma fração de
um grafo em que possui subconjuntos dos vértices e arestas do grafo original.
Portanto V’⊆ V e E’⊆ E.
Fonte: Slides disponibilizados pela professora Carolina Watanabe
30. O que é um subgrafo gerador?
R: Um subgrafo gerador é subgrafo de um grafo maior que contém todo o conjunto de
vértices V(G), mas não todo o conjunto de arestas E(G), contudo E’⊂ E.
31. O que é uma árvore geradora?
R: Uma árvore geradora é um subgrafo gerador mas também é uma árvore, ou seja é
conexo e acíclico.
https://www.javatpoint.com/graph-theory-types-of-graphs
32. O que é um subgrafo induzido?
R: Um subgrafo induzido é um subgrafo que possui os subconjuntos V’ e E’ de um
grafo G = (V,E) em que o subconjunto do conjunto de vértices V’ ⊆ V do grafo
original mantém a mesma relação de conectividade de arestas dos vértices
selecionados no subconjunto V’.
Fonte: Subgrafo – Wikipédia, a enciclopédia livre
33. O que é uma árvore geradora mínima?
R: É uma árvore geradora que busca minimizar o custo em cada caminho do grafo, ou
seja, a soma de todos os pesos das arestas do grafo é o menor possível.
34. Escreva o algoritmo da ordenação topológica (pseudocódigo)
R:
Início
Dado G um dígrafo acíclico;
Inicializar S vazia;
Enquanto houver vértice para ser eliminado do Grafo, faça:
Seja v, um vértice que tenhagrau de entrada nulo;
Insira v como próximo vértice da sequência S;
Exclua v do Grafo (resulta num novo dígrafo acíclico)
Fim
35. Escreva o algoritmo de Prim (pseudocódigo)
R:
procedimento Prim(G)
escolha um vértice s para iniciar a árvore
enquanto há vértices que não estão na árvore
selecione uma aresta segura
insira a aresta e seu vértice na árvore
36. Escreva o algoritmo de Kruskal (pseudocódigo)
R:
Crie uma floresta F ( um conjunto de árvores).
Crie um conjunto S contendo todas as arestas (pesos) do grafo.
- Enquanto S não for vazio, faça:
- Remova uma aresta com peso mínimo de S
- Se essa aresta conecta duas árvores diferentes,
https://pt.wikipedia.org/wiki/Subgrafo
37. Escreva o algoritmo de Roy-Warshall (RW) (pseudocódigo)
R:
Dada X𝑛𝑥𝑛, matriz adjacência de D(V,A)
Início
Faça P = X;
para j = 1 até n faça
para i = 1 até n faça
se = 1 /*se já há caminho de i a j*/𝑃
𝑖𝑗
então para k = 1 até n faça
= v /*então haverá de i a k se houver de j a */𝑃
𝑖𝑘
𝑃
𝑖𝑘
𝑃
𝑗𝑘
Fim
38. Escreva o algoritmo de Floyd-Warshall (FW) (pseudocódigo)
R:
Dada X de D, cria MC, a matriz dos custos dos caminhos
mínimos
Início
faça MC = X
para j = 1 até n faça
para i = 1 até n faça
se MCij então /*se há caminho de custo MCij de i a j*/
para k = 1 até n faça
MCik = min (MCik, MCij + MCjk)/*então o custo min. de i
a k é o mínimo entre o caminho direto de i a k e a soma de i a j e de j a k*/
Fim
39. Escreva o algoritmo de Dijkstra (pseudocódigo)
R:
DIJKSTRA(G, w, s) /* Dados Grafo G, origem s e Lista de adjacência
de s, w*/
início
//inicializa variáveis
para cada vértice v faça
d[v]=∞
antecessor[v]=-1
d[s]=0
S=Ø
cria fila de prioridade F com vértices do grafo
enquanto F≠ Ø faça /*insere vértice u em S e faz relaxamento das
arestas adjacentes*/
u=retirar vértice de F, reorganizando F
S=S+{u}
para cada vértice v adjacente a u faça
relax(u,v,w)
fim
EXERCÍCIOS DE FIXAÇÃO
40. Desenhe as versões não orientadas e orientadas do grafo G= (V,E), onde
V={1,2,3,4,5,6} e E={(2,5),(6,1),(5,3),(2,3)} .
R: Não orientado: Orientado:
41. Desenhe os grafos não orientados completos com 4 vértices (K4), 5 vértices (K) e 6
vértices (K6).
R: K = 4(4-1)/2 = 6 K = 5(5-1)/2 = 10 K = 6(6-1)/2 = 15₄ ₅ ₆
4 vértices 5 vértices 6 vértices
6 arestas 10 arestas 15 arestas
42. Quantas arestas possui um grafo completo com n vértices? E um grafo orientado
completo com n vértices?
R: Um grafo completo com n vértices possui n(n-1)/2 arestas.
Um grafo orientado completo n vértices possui n(n-1) arestas.
43. Encontre o complemento do seguinte grafo.
R:
44. Quantas componentes conexas tem o seguinte grafo?
R: Somente duas: e
45. Determine se cada um dos grafos abaixo é bipartido. Justifique.
R: a) É bipartido, pois pode ser dividido em dois conjuntos de vértices que não
se conectam {a, b, c, d} e {e}.
b) É bipartido, pois pode ser dividido em dois conjuntos de vértices que não se
conectam {a, c} e {e, b, d}.
c) Não é bipartido, pois não há forma de separar em dois conjuntos.
d) é bipartido, pois pode ser separado em dois conjuntos de vértices disjuntos:
{a, b, d, e} e {c, f}.
e) Não é bipartido, não há maneira de separar o grafo em dois conjuntos que não
sejam adjacentes um ao outro.
46. Pode haver um grafo simples com 15 vértices, cada um com grau 5?
R: Não, pois seguindo o Teorema (do aperto de mãos ou handshaking): Seja G
um grafo. A soma dos graus de todos os vértices do G é duas vezes o número de
arestas de G. Portanto, a soma de todos os graus desse suposto vértice seria 15*5
= 75, sendo assim se a soma é duas vezes o número de arestas este grafo
possuiria 75/2 arestas, que é um número decimal 37,5. Sendo assim, não faz
sentido um grafo possuir 37,5 aresta.
47. Existe um grafo simples com cinco vértices dos seguintes graus? Se existir,
desenhe um possível grafo.
(a) 3; 3; 3; 3; 2 (b) 1; 2; 3; 4; 5 (c) 1; 2; 3; 4; 4 (d) 3; 4; 3; 4; 3
(e) 0; 1; 2; 2; 3 (f) 1; 1; 1; 1; 1
a) R:
b) R: Não, pois novamente pelo teorema do aperto de mãos, a soma dos graus
desse grafo seria 15. Sendo 15/2 = 7,5. O grau total de um grafo é um valor par e
inteiro.
c) R: Apesar de teoricamente ser possível existir esse grafo pois ele teria grau 14 e 7
arestas (14/2), por meio dessa combinação de graus em cada vértice (1; 2; 3; 4; 4) se
torna inviável formar um grafo simples.
d) R: Não, pois novamente pelo teorema do aperto de mãos, a soma dos graus desse
grafo seria 17. Sendo 17/2 = 8,5. O grau total de um grafo é um valor par e inteiro.
e) R:
f) R: Não, pois a soma dos graus desse grafo seria 5. Sendo 5/2 = 2,5. O grau total
de um grafo é um valor par e inteiro.
48. Qual a ordem e o número de arestas de cada grafo?
a) R: Ordem = 5, pois são 5 vértices e 7 arestas.
b) R: Ordem = 5, pois são 5 vértices e 4 arestas.
49. a) Quais dos grafos abaixo são completos?
R: Apenas letra c.
b) Quais dos grafos abaixo são simples?
R: Apenas letras B e C.
c) No grafo (a), quais vértices são adjacentes a v3? E quais arestas são
adjacentes a (v3,v5)?
R: Grafo (a) São adjacentes a v3: v1, v2, v4 e v5.
São arestas adjacentes a (v3, v5): (v3, v1), (v3,v4), (v3,v2).
50. O grafo (a) é regular? Por quê? Existe alguma fonte ou sumidouro no grafo (b)?
(a) (b)
a) R: Sim, pois todos os seus vértices possuem o mesmo grau, 3.
b) R: Sim, V5 é Fonte e v3 e v4 são sumidouros.
51. Qual dos grafos abaixo são cíclicos? Indique os grafos que são conexos. Qual(is)
dos grafos abaixo são Eulerianos? Quais são Hamiltonianos?
(a) (b) ©
R: Todos são cíclicos e todos são conexos. E os grafos B e C são Hamiltonianos.
52. Quais os complementos dos grafos (a) e (c)? Os grafos (b) e (c) são isomorfos?
Represente graficamente um grafo K4,3.
(a) (b) (c)
R: Complemento dos grafos (a) e (c):
a) (c)
Os Grafos (b) e (c) não são isomorfos, pois apesar de possuírem a mesma
quantidade de vértices, ambos diferem na quantidade de arestas.
Grafo K4.3:
53. Represente o grafo abaixo usando matriz de adjacências e lista de adjacências.
Matriz de Adjacências: Lista de Adjacências:
1 2 3 4 5 6
1 0 1 0 0 1 0
2 1 0 1 0 1 0
3 0 1 0 1 0 0
4 0 0 1 0 1 1
5 1 1 0 1 0 0
6 0 0 0 1 0 0
54. Represente os grafos abaixo utilizando matrizes de adjacências e listas de
adjacências.
Matriz de adjacências: Lista de adjacências:
1 → 2 → 5
2 → 1 → 5 → 3
3 → 2 → 4
4 → 3 → 6 → 5
5 → 4 → 2 → 1
6 → 4
a b c d e f
a 0 1 0 0 0 1
b 1 0 1 1 0 1
c 0 1 0 1 0 1
d 0 1 1 0 1 1
e 0 0 0 1 0 1
f 1 1 1 1 1 1
a → b → f
b → a → d → f → c
c → b → f → d
d → c → b → f → e
e → d → f
f → a → b → c → d → e
Matriz de adjacências: Lista de adjacências:
55. Preencha a tabela de comparação entre matriz de adjacências e listas de
adjacências, assim como suas respectivas ordens de complexidade.
1. Rapidez para saber se (x,y) está no grafo:
R: Matriz de Adjacência: O(1)
Lista de Adjacências: O( ) no qual d é o grau do vértice u.𝑑
𝑢
2. Rapidez para determinar o grau de um vértice:
R: Matriz de Adjacência: O(|V|).
Lista de Adjacências: O( ) no qual d é o grau do vértice.𝑑
𝑢
3. Menor memória em grafos pequenos
R: Matriz de adjacência: vazio.
Lista de adjacências: vazio.
4. Maior memória em grafos densos:
R: Matriz de adjacência: O(|V|²).
Lista de Adjacências: O(|V| + |E|).
1 2 3 4 5
1 0 0 1 1 1
2 0 0 0 0 0
3 0 1 0 1 1
4 0 0 0 0 0
5 0 0 0 0 0
1 → 4 → 3 → 5
2
3 → 4 → 5 → 2
4
5
5. Inserção e remoção de vértices:
R: Matriz de adjacência: O(1), onde n é o número de vértices e m é o número de
arestas no grafo.
Lista de Adjacências: O( ).𝑑
𝑢
6. Melhor na maioria dos problemas:
R: Lista de Adjacências
7. Rapidez para percorrer um grafo:
R: Matriz de Adjacência: O(|V|²).
Lista de Adjacências: O(|V| + |E|), onde n é o número de vértices e m é o número
de arestas no grafo.
56. Dados os seguintes grafos, indique todos os pares e tais que:
(a) Gx é subgrafo de Gy;
(b) Gx é subgrafo gerador de Gy;
(c) Gx é subgrafo induzido de Gy;
(d) Gx não é subgrafo de Gy.
a) (G2,G1), (G3,G1), (G4,G1), (G5,G1), (G3,G2) (G4,G2), (G2,G5), (G3,G5),
(G4,G5).
b) (G5,G1).
c) (G2,G1), (G2,G5),(G4,G1), (G4,G2), (G4,G5), (G3,G1), (G3,G2), (G3,G4),
(G3,G5).
d) (G5,G2), (G2,G3), (G2,G4), (G1,G2), (G1,G3), (G1,G4), (G1,G5).
57. Diga se os pares de grafos abaixo são isomorfos e porquê.
(a) b)
a) Não são isomorfos, pois ao analisar os vértices em ambos grafos que possuem
grau 3, é possível identificar que no primeiro grafo há um vértice adjacente entre
eles (u5 é adjacente a u3 e u6), porém no segundo grafo não há um vértice
adjacente aos dois vértices com grau 3 (v2 e v6).
b) São isomorfos, pois ambos possuem o mesmo número de vértices, arestas e
mesmo grau em todos os vértices, além disso é possível identificar que fazem as
mesmas conexões por arestas.
58. Determine os componentes fortemente conexos do grafo abaixo.
R: É fortemente conexo o caminho entre os vértices a, b, e.
59. Aplique o algoritmo de (a) busca em largura, apresentando os vértices marcados,
a fila Q e as arestas visitadas; (b) busca em profundidade, apresentando a pilha,
os vértices marcados e as arestas visitadas. Considere como vértice inicial o 1
(raiz da busca).
R =
Aresta inicial: 1
Pilha: (1,4,2,3,6,5)
Vértices Marcados: 1,4,2,3,6,5
Arestas Visitadas: (1,4) (4,2) (2,1) (2,3) (3,1) (3,4) (3,6) (6,1) (6,4) (6,5) (5,4)
60. Aplique o algoritmo de ordenação topológica no grafo a seguir e mostre uma
ordem dos vértices produzida pela ordenação topológica do seguinte grafo:
61. Qual é a complexidade da Busca em Largura (BFS ‐ Breadth‐First Search)? E
da Busca em Profundidade (DFS ‐ Depth‐First Search)?
R = O(|V| + |E|)
62. Qual é o número cromático do grafo K3,2?
R = x(2)
63. Suponhamos que uma empresa que faça instalação de fibra ótica necessite
interligar os bairros abaixo representados:
A partir de um estudo meticuloso, os dados relevantes à instalação da fibra ótica, podem
ser resumidos ao Grafo mostrado acima. Gere a Árvore Geradora Mínima para este
caso, usando a ideia do Algoritmo de Kruskal e de Prim.
R:
64. (Adaptado de Fundamentos Matemáticos para a Ciência da Computação Ex. 19,
p. 361) Use o Algoritmo de Prim para resolver a Árvore Geradora Mínima para
o Grafo indicado. Use também o Algoritmo de Kruskal e compare os resultados.
R:
65. Dada a seguinte matriz de adjacência, gere a árvore geradora mínima usando
Prim ou Kruskal.
R:
66. Dê quatro ordenações topológicas diferentes do digrafo cujos arcos são
a-c a-d b-c b-d c-e d-e.
R:
67. Obtenha as ordenações topológicas para o grafo abaixo.
R:
68. Aplique o algoritmo de Dijkstra nos grafos abaixo, mostrando o os valores de
d[v], S e o antecessor a cada iteração. Ao final, apresente os caminhos a partir de
s e os custos.
antecessor
s t y x z
- s s - -
- y s y y
- z
- y s t y
S d(t) d(y) d(x) d(z)
S 10 5 inf inf
{s,y} 8 5 14 7
{s,y,z} 8 5 13 7
{s,y,z,t} 8 5 9 7
69. Execute o algoritmo de Floyd-Warshall sobre o digrafo cuja matriz inicial W é
dada a seguir. Exiba todas as matrizes intermediárias.
0 3 8 ∞
∞ 0 ∞ 1
∞ 4 0 ∞
2 5 5 0
0 3 8 4
∞ 0 ∞ 1
∞ 4 0 5
2 5 5 0
0 3 8 4
∞ 0 ∞ 1
∞ 4 0 5
2 5 5 0
0 3 8 4
3 0 6 1
7 4 0 5
2 5 5 0
Observação: Abaixo estão alguns teoremas interessantes que podem auxiliar.
Teorema: Todo grafo euleriano é conexo e todos os seus vértices possuem grau par.
Teorema (do aperto de mãos ou handshaking): Seja G um grafo. A soma dos graus de
todos os vértices do G é duas vezes o número de arestas de G. Especificamente, se os
vértices de G são V1, v2, ..., vn, onde n é um inteiro positivo, então
Grau de G = grau(v1) + grau(v2) + ... + grau(vn)
= 2 * número de arestas de G.
Corolário: O grau total de um grafo é par.
Teorema: Em qualquer grafo G, existe um número par de vértices de grau ímpar.
Teorema: Se um grafo possui um circuito Euleriano, então cada vértice do grafo tem
grau par.
Teorema: Se algum vértice de um grafo tem grau ímpar, então o grafo não tem um
circuito Euleriano.
Teorema: Se cada vértice de um grafo não vazio tem grau par e o grafo é conexo, então
o grafo tem um circuito Euleriano.
Corolário: Um grafo conexo tem um caminho euleriano se tiver no máximo 2 vértices
de grau ímpar.
Definição: O número cromático de um grafo representa o menor número de cores
necessárias para colorir os vértices de um grafo sem que vértices adjacentes tenham a
mesma cor.
REFERÊNCIAS:
<https://pt.wikipedia.org/wiki/Grafo_completo>
<https://www.javatpoint.com/graph-theory>
<https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tu
torials/>
https://pt.wikipedia.org/wiki/Grafo_completo
https://www.javatpoint.com/graph-theory
https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tutorials/
https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tutorials/